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}). 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