Another Exercise on Graphs (Easy Version)
Contest: Hello 2025
Difficulty rating: 2300
Tags: binary search, brute force, dp, dsu, graphs, shortest paths, sortings

This is the easy version of the problem. The difference between the versions is that in this version, there is an additional constraint on $$$m$$$. You can hack only if you solved all versions of this problem.

Recently, the instructors of "T-generation" needed to create a training contest. They were missing one problem, and there was not a single problem on graphs in the contest, so they came up with the following problem.

You are given a connected weighted undirected graph with $$$n$$$ vertices and $$$m$$$ edges, which does not contain self-loops or multiple edges.

There are $$$q$$$ queries of the form $$$(a, b, k)$$$: among all paths from vertex $$$a$$$ to vertex $$$b$$$, find the smallest $$$k$$$-th maximum weight of edges on the path$$$^{\dagger}$$$.

The instructors thought that the problem sounded very interesting, but there is one catch. They do not know how to solve it. Help them and solve the problem, as there are only a few hours left until the contest starts.

$$$^{\dagger}$$$ Let $$$w_1 \ge w_2 \ge \ldots \ge w_{h}$$$ be the weights of all edges in a path, in non-increasing order. The $$$k$$$-th maximum weight of the edges on this path is $$$w_{k}$$$.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each set of test case contains three integers $$$n, m$$$ and $$$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$$$) — the number of vertices, the number of edges, and the number of questions, respectively.

Each of the following $$$m$$$ lines of each set of test case contains three integers $$$v, u$$$ and $$$w$$$ ($$$1 \le v, u \le n$$$, $$$1 \le w \le 10^9$$$) — the ends of the next edge of the graph and its weight, respectively. It is guaranteed that the graph does not contain self-loops and multiple edges.

Each of the following $$$q$$$ lines of each set of test case contains three integers $$$a, b$$$ and $$$k$$$ ($$$1 \le a, b \le n$$$, $$$k \ge 1$$$) — the next question. It is guaranteed that any path from vertex $$$a$$$ to vertex $$$b$$$ contains at least $$$k$$$ edges.

It is guaranteed that the sum of the values of $$$n$$$ across all sets of test cases does not exceed $$$400$$$.

It is guaranteed that the sum of the values of $$$m$$$ across all sets of test cases does not exceed $$$400$$$.

It is guaranteed that the sum of the values of $$$q$$$ across all sets of test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output the answers to all questions.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

Note:
In the first set of test cases, one of the optimal paths in the first query is the path $$$1 \rightarrow 3 \rightarrow 4$$$; the $$$2$$$-nd maximum weight of the edges on this path is $$$1$$$. In the second query, one of the optimal paths is $$$2 \rightarrow 4 \rightarrow 3$$$; $$$1$$$-st maximum weight of the edges is $$$2$$$.

In the second set of input data, one of the optimal paths in the first query is the path $$$1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 6$$$; the $$$3$$$-rd maximum weight of the edges on this path is $$$2$$$.

Example input:
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

Example output:
1 2
2 9 9
11 3 11 1 3 10 8 4 11 4

Editorial:
We will learn how to check if there exists a path from $$$a$$$ to $$$b$$$ such that the $$$k$$$-th maximum on this path is less than or equal to $$$x$$$. For a fixed $$$x$$$, the edges are divided into two types: light (weight less than or equal to $$$x$$$) and heavy (weight strictly greater than $$$x$$$). We assign a weight of $$$0$$$ to all light edges and a weight of $$$1$$$ to all heavy edges. Then, the desired path exists if and only if the shortest path between $$$a$$$ and $$$b$$$ (considering the assigned weights) is strictly less than $$$k$$$.
Now, let's consider that we have many queries.
Initially, we assign a weight of $$$1$$$ to all edges and compute the length of the shortest path between each pair of vertices. Then, we will process the edges in increasing order of weight and replace their weights with $$$0$$$. After each such change, we need to be able to recalculate the shortest paths between each pair of vertices. Let $$$\textrm{d}[i][j]$$$ be the shortest paths before changing the weight of the edge $$$(a, b)$$$; then the lengths of the new paths $$$\textrm{d}'$$$ can be computed using the formula:
$$$$$$ \textrm{d}'[i][j] = \min \{ \textrm{d}[i][j], \textrm{d}[a][i] + \textrm{d}[b][j], \textrm{d}[b][i] + \textrm{d}[a][j], \} $$$$$$
Thus, each recalculation of the lengths of the shortest paths can be performed in $$$O(n^2)$$$. Let $$$\textrm{dp}[k][i][j]$$$ be the length of the shortest path between the pair of vertices $$$i$$$ and $$$j$$$, if the weights of the minimum $$$k$$$ edges are $$$0$$$, and the weights of the remaining edges are $$$1$$$. We have just learned how to recalculate this dynamic programming in $$$O(n^2 \cdot m)$$$ time.
Using the criterion, we can answer each of the queries in $$$O(\log m)$$$ time using the binary search method and the computed array $$$\textrm{dp}[k][i][j]$$$.
On simple and non-simple paths. If there is a cycle in the path, it can be removed from this path, and the $$$k$$$-th maximum will not increase. Thus, if we restrict the set of considered paths to only simple paths (i.e., those that do not contain cycles in any form), the answer will not change.