CF2117G Omg Graph

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

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

For each test case, output a single integer, the minimum cost path from vertex $ 1 $ to $ n $ .

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