← 返回题目列表

Codeforces · 2117/G

G. 天啊图

中文机器翻译题面 查看原题

给您一个无向连通加权图。将长度为 $$$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$$$ 的最小成本路径。

示例

输入
复制

4
3 2
1 2 1
2 3 1
3 2
1 3 13
1 2 5
8 9
1 2 6
2 3 5
3 8 6
1 4 7
4 5 4
5 8 7
1 6 5
6 7 5
7 8 5
3 3
1 3 9
1 2 8
2 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$$$。可以证明,不存在成本更低的路径。