Another Exercise on Graphs (hard version)
Contest: Hello 2025
Difficulty rating: 2500
Tags: binary search, dfs and similar, dp, dsu, graphs, shortest paths, sortings

This is the hard version of the problem. The difference between the versions is that in this version, there is no 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 \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 $$$q$$$ across all sets of test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each set of 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:
Please read the solution to problem E1.
Let's return to the process where we sequentially changed the weights of the edges from $$$1$$$ to $$$0$$$. If we replace the weight of another edge with $$$0$$$ and it connects vertices that are at a distance of $$$0$$$, it means that the shortest paths between each pair of vertices will not change at all, so we will not recalculate the shortest paths in this case.
We also will not store useless layers in the array $$$\textrm{dp}[k][i][j]$$$. This allows us to improve the asymptotic complexity of our solution to $$$O(n^3 + q \log n)$$$.
Proof. We will consider a graph that consists only of edges with weight $$$0$$$. We have $$$m$$$ consecutive requests to add an edge. Notice that we compute a new layer of $$$\textrm{dp}$$$ only if, after adding the edge, some two components of this graph are merged, but this will happen exactly $$$n-1$$$ times.