给您一个无向连通加权图。将长度为 $$$k$$$ 的路径的成本定义如下:
- 设路径上所有边的权重为$$$w_1,...,w_k$$$。
- 路径的成本为 $$$(\min_{i = 1}^{k}{w_i}) + (\max_{i=1}^{k}{w_i})$$$,或者换句话说,最大边权重 + 最小边权重。
在从顶点 $$$1$$$ 到 $$$n$$$ 的所有路径中,报告具有最小成本的路径的成本。请注意,路径不一定简单。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5, n - 1 \le m \le \min(2 \cdot 10^5, \frac{n(n - 1)}{2})$$$)。
接下来的 $$$m$$$ 行每行包含整数 $$$u、v$$$ 和 $$$w$$$ ($$$1 \le u, v \le n, 1 \le w \le 10^9$$$),表示从顶点 $$$u$$$ 到 $$$v$$$ 的一条边,权重为 $$$w$$$。保证图不包含自环或重边,并且所得图是连通的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,并且所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,即从顶点 $$$1$$$ 到 $$$n$$$ 的最小成本路径。
示例
输入复制
43 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 3
输出复制
2 18 10 11
注意
对于第二个测试用例,最佳路径为 $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$,边权重为 $$$5, 5, 13$$$,因此成本为 $$$\min(5, 5, 13) + \max(5, 5, 13) = 5 + 13 = 18$$$。可以证明,不存在成本更低的路径。