write a go solution for G. Omg Graphtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an undirected connected weighted graph. Define the cost of a path of length k to be as follows:  Let the weights of all the edges on the path be w_1,...,w_k.  The cost of the path is (min_i=1^kw_i)+(max_i=1^kw_i), or in other words, the maximum edge weight + the minimum edge weight. Across all paths from vertex 1 to n, report the cost of the path with minimum cost. Note that the path is not necessarily simple.InputThe first line contains an integer t (1<=t<=10^4) — the number of test cases.The first line of each test case contains two integers n and m (2<=n<=2*10^5,n-1<=m<=min(2*10^5,n(n-1)/2)).The next m lines each contain integers u,v and w (1<=u,v<=n,1<=w<=10^9) representing an edge from vertex u to v with weight w. It is guaranteed that the graph does not contain self-loops or multiple edges and the resulting graph is connected.It is guaranteed that the sum of n over all test cases does not exceed 2*10^5 and that the sum of m over all test cases does not exceed 2*10^5.OutputFor each test case, output a single integer, the minimum cost path from vertex 1 to n.ExampleInput43 21 2 12 3 13 21 3 131 2 58 91 2 62 3 53 8 61 4 74 5 45 8 71 6 56 7 57 8 53 31 3 91 2 82 3 3Output2
18
10
11
NoteFor the second test case, the optimal path is 1arrow2arrow1arrow3, the edge weights are 5,5,13 so the cost is min(5,5,13)+max(5,5,13)=5+13=18. It can be proven that there is no path with lower cost.. Output only the code with no comments, explanation, or additional text.