write a go solution for E1. Another Exercise on Graphs (Easy Version)time limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputThis 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>=w_2>=ldots>=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.InputEach test contains multiple test cases. The first line contains a single integer t (1<=t<=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<=n<=400, n-1<=m<=operatornamemin(mathbf400,n*(n-1)/2), 1<=q<=3*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<=v,u<=n, 1<=w<=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<=a,b<=n, k>=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*10^5.OutputFor each test case, output the answers to all questions.ExampleInput34 4 21 2 22 4 21 3 43 4 11 4 22 3 16 7 31 2 102 3 33 4 94 5 25 6 12 4 104 6 101 6 31 6 22 4 111 17 101 4 51 3 191 2 103 2 134 5 14 6 113 5 93 6 182 7 175 8 155 10 86 9 47 10 207 8 168 11 39 11 610 11 143 11 13 11 31 11 11 11 41 11 38 2 210 4 13 9 23 9 16 7 3Output1 2
2 9 9
11 3 11 1 3 10 8 4 11 4
NoteIn the first set of test cases, one of the optimal paths in the first query is the path 1arrow3arrow4; the 2-nd maximum weight of the edges on this path is 1. In the second query, one of the optimal paths is 2arrow4arrow3; 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 1arrow2arrow4arrow5arrow6; the 3-rd maximum weight of the edges on this path is 2.. Output only the code with no comments, explanation, or additional text.