E1. Очередное упражнение на графы (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии есть дополнительное ограничение на $$$m$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Недавно преподавателям «Т-поколения» нужно было сделать учебный контест. Им не хватает одной задачи, и в контесте как раз нет ни одной задачи на графы, поэтому они придумали следующую задачу.

Вам дан связный взвешенный неориентированный граф из $$$n$$$ вершин и $$$m$$$ ребер, который не содержит петель и кратных ребер.

Есть $$$q$$$ вопросов вида $$$(a, b, k)$$$: среди всех путей от вершины $$$a$$$ до вершины $$$b$$$ найти наименьший $$$k$$$-й максимум весов ребер на пути$$$^{\dagger}$$$.

Преподавателям показалось, что задача звучит очень интересно, но есть одно но... они не умеют ее решать. Помогите им и решите задачу, ведь до начала контеста осталось всего пару часов.

$$$^{\dagger}$$$ Пусть $$$w_1 \ge w_2 \ge \ldots \ge w_{h}$$$ — веса всех ребер на пути в порядке невозрастания. Тогда $$$k$$$-й максимум весов ребер на этом пути равен $$$w_{k}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n, m$$$ и $$$q$$$ ($$$2 \le n \le 400$$$, $$$n - 1 \le m \le \operatorname{min}(\mathbf{400}, \frac{n \cdot (n - 1)}{2})$$$, $$$1 \le q \le 3 \cdot 10^5$$$) — количество вершин, количество ребер и количество вопросов соответственно.

Каждая из следующих $$$m$$$ строк каждого набора входных данных содержит три целых числа $$$v, u$$$ и $$$w$$$ ($$$1 \le v, u \le n$$$, $$$1 \le w \le 10^9$$$) — концы очередного ребра графа и его вес соответственно. Гарантируется, что граф не содержит петель и кратных ребер.

Каждая из следующих $$$q$$$ строк каждого набора входных данных содержит три целых числа $$$a, b$$$ и $$$k$$$ ($$$1 \le a, b \le n$$$, $$$k \ge 1$$$) — очередной вопрос. Гарантируется, что любой путь из вершины $$$a$$$ в вершину $$$b$$$ содержит не менее $$$k$$$ ребер.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$400$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$400$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите ответы на все вопросы.

Пример
Входные данные
3
4 4 2
1 2 2
2 4 2
1 3 4
3 4 1
1 4 2
2 3 1
6 7 3
1 2 10
2 3 3
3 4 9
4 5 2
5 6 1
2 4 10
4 6 10
1 6 3
1 6 2
2 4 1
11 17 10
1 4 5
1 3 19
1 2 10
3 2 13
4 5 1
4 6 11
3 5 9
3 6 18
2 7 17
5 8 15
5 10 8
6 9 4
7 10 20
7 8 16
8 11 3
9 11 6
10 11 14
3 11 1
3 11 3
1 11 1
1 11 4
1 11 3
8 2 2
10 4 1
3 9 2
3 9 1
6 7 3
Выходные данные
1 2
2 9 9
11 3 11 1 3 10 8 4 11 4
Примечание

В первом наборе входных данных одним из оптимальных путей в первом запросе является путь $$$1 \rightarrow 3 \rightarrow 4$$$, $$$2$$$-й максимум весов ребер на этом пути это $$$1$$$. Во втором запросе одними из оптимальных путей являются путь $$$2 \rightarrow 4 \rightarrow 3$$$, $$$1$$$-й максимум весов ребер это $$$2$$$.

Во втором наборе входных данных одним из оптимальных путей в первом запросе является путь $$$1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6$$$, $$$3$$$-й максимум весов ребер на этом пути это $$$2$$$.