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

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

For each set of test case, output the answers to all questions.

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$.