您正处于一个由 $$$n$$$ 个顶点和 $$$m$$$ 加权边组成的无向连通图上。边的索引从 $$$1$$$ 到 $$$m$$$。第 $$$i$$$ 条边连接顶点 $$$u_i$$$ 和 $$$v_i$$$,并具有权重 $$$w_i$$$。您决定围绕图表进行一次奇妙的旅行。
假设您位于顶点 $$$x$$$。您可以多次执行以下操作:
- 马克 一条连接$$$x$$$和$$$y$$$的边,沿着边拍照,然后移动到$$$y$$$,这正好消耗边的权重。
- 转账 乘火车到另一个任意顶点 $$$z \neq x$$$。您可以选择任何路径 $$$x\leadsto z$$$ (不一定简单),成本为 重量 的边缘 最大索引 在那条路上。形式上,假设您选择边索引为 $$$e_1, e_2, \ldots, e_k$$$ 的路径,这样存在一个顶点数组 $$$p_1, p_2, \ldots, p_{k+1}$$$,其中 $$$x = p_1$$$, $$$z = p_{k+1}$$$,并且对于 $$$[1 中的所有 $$$i$$$, k]$$$,边$$$e_i$$$连接$$$p_{i}$$$和$$$p_{i+1}$$$,成本为$$$w_{\max_{i=1}^k e_i}$$$。
你现在位于顶点$$$1$$$,你需要 标记 每条边至少一次并返回顶点$$$1$$$。计算最小成本。
请注意费用 正在转移 不是路径上的最大权重,也不是最大索引本身。如果您有任何疑问,请参阅 下面的 注意 部分。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$T$$$ ($$$1 \le T \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$0 \le m \le 10^6$$$)。
然后 $$$m$$$ 行,第 $$$i$$$ 行包含三个整数 $$$u_i, v_i, w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$1 \le w \le 10^9$$$) — 意味着索引为 $$$i$$$ 的边位于顶点之间$$$u_i$$$ 和顶点 $$$v_i$$$ ,权重为 $$$w_i$$$。
保证所描述的图是连通的。
另请注意,该图可能有 自循环 和 多个边缘.
保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出一个整数——最小成本。
示例
输入复制
55 62 4 152 5 41 3 62 3 91 2 103 4 74 31 2 31 3 21 4 12 31 2 12 1 31 1 46 62 3 101 3 105 6 106 6 14 5 103 4 105 51 2 45 1 54 3 62 4 101 4 7
输出复制
58887143
注意
展示台链接
令 $$$u \xrightarrow{e} v$$$ 表示从顶点 $$$u$$$ 通过边 $$$e$$$ 到顶点 $$$v$$$。
在第一个测试用例中,一个可能的解决方案是:
- 最初,您位于顶点 $$$1$$$。
- 标记边 $$$3$$$ 并移动到顶点 $$$3$$$,成本 $$$6$$$。
- 标记边 $$$6$$$ 并移动到顶点 $$$4$$$,成本 $$$7$$$。
- 标记边 $$$1$$$ 并移动到顶点 $$$2$$$,成本 $$$15$$$。
- 标记边 $$$4$$$ 并移动到顶点 $$$3$$$,成本 $$$9$$$。
- 转移到顶点$$$5$$$。通过选择路径$$$3 \xrightarrow{6} 4 \xrightarrow{1} 2 \xrightarrow{2} 5$$$,我们可以实现成本$$$7$$$,因为路径上边之间的最大索引是$$$6$$$,并且$$$w_6 = 7$$$。 请注意,使用操作 2 时我们不关心路径上的最大权重。
- 标记边 $$$2$$$ 并移动到顶点 $$$2$$$,成本 $$$4$$$。
- 标记边 $$$5$$$ 并移动到顶点 $$$1$$$,成本 $$$10$$$。
总成本为$$$6+7+15+9+7+4+10=58$$$。
在第二个测试用例中,一种可能的解决方案是:
- 标记边 $$$1$$$ 并移动到顶点 $$$2$$$,成本 $$$3$$$。
- 通过 $$$2 \xrightarrow{1} 1 \xrightarrow{3} 4 \xrightarrow{3} 1 \xrightarrow{2} 3$$$ 转移到顶点 $$$3$$$,成本为 $$$1$$$。 请注意,操作 2 中选择的路径可能并不简单。
- 标记边 $$$2$$$ 并移动到顶点 $$$1$$$,成本 $$$2$$$。
- 标记边 $$$3$$$ 并移动到顶点 $$$4$$$,成本 $$$1$$$。
- 通过 $$$4 \xrightarrow{3} 1$$$ 转移到顶点 $$$1$$$,成本为 $$$1$$$。