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}^{k}{w_i}) + (\max_{i=1}^{k}{w_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 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5, n - 1 \le m \le \min(2 \cdot 10^5, \frac{n(n - 1)}{2})$$$).The next $$$m$$$ lines each contain integers $$$u, v$$$ and $$$w$$$ ($$$1 \le u, v \le n, 1 \le w \le 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 \cdot 10^5$$$ and that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 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 $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$, 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.