图上旅行

题目描述

您当前位于一个包含 $n$ 个顶点和 $m$ 条带权边的无向连通图上。边的编号从 $1$ 到 $m$。第 $i$ 条边连接顶点 $u_{i}$ 和 $v_{i}$，并具有权重 $w_{i}$。您决定在图上进行一次美妙的旅行。

假设您当前在顶点 $x$。您可以任意多次执行以下操作：

1. 标记一条连接 $x$ 和 $y$ 的边，沿着该边拍照，并移动到 $y$，此操作的成本恰好等于该边的权重。

2. 通过火车传送到另一个任意顶点 $z\neq x$。您可以选择任意一条从 $x$ 到 $z$ 的路径（不必是简单路径），其成本是该路径上具有最大索引的边的权重。形式化地说，假设您选择的路径包含边索引 $e_{1}$, $e_{2}$, ..., $e_{k}$，并且存在一个顶点序列 $p_{1}$, $p_{2}$, ..., $p_{k+1}$，使得 $x = p_{1}$, $z = p_{k+1}$，并且对于所有在区间 [1, k] 内的 $i$，边 $e_{i}$ 连接 $p_{i}$ 和 $p_{i+1}$，那么成本为 $w_{\max_{i=1}^{k}e_{i}}$。

您当前在顶点 $1$，您需要至少标记每条边一次并返回到顶点 $1$。请计算最小成本。

请注意，传送的成本不是路径上的最大权重，也不是最大索引本身。如果您有任何疑问，请参考下面的注释部分。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数量 $T$（$1\leqslant T\leqslant 10^{4}$）。测试用例描述如下。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1\leqslant n\leqslant 10^{6}$，$0\leqslant m\leqslant 10^{6}$）。

接着是 $m$ 行，第 $i$ 行包含三个整数 $u_{i}$, $v_{i}$, $w_{i}$（$1\leqslant u_{i}, v_{i}\leqslant n$，$0\leqslant w_{i}\leqslant 10^{9}$）- 表示索引为 $i$ 的边连接顶点 $u_{i}$ 和顶点 $v_{i}$，权重为 $w_{i}$。

保证所描述的图是连通的。

同时注意，图中可能存在自环和重边。

保证所有测试用例的 $n$ 和 $m$ 的总和分别不超过 $10^{6}$。

输出格式

对于每个测试用例，输出一个整数 - 最小成本。

样例

5
5 6
2 4 15
2 5 4
1 3 6
2 3 9
1 2 10
3 4 7
4 3
1 2 3
1 3 2
1 4 1
2 3
1 2 1
2 1 3
1 1 4
6 6
2 3 10
1 3 10
5 6 10
6 6 1
4 5 10
3 4 10
5 5
1 2 4
5 1 5
4 3 6
2 4 10
1 4 7

58
8
8
71
43

提示

用 $u \xrightarrow{e} v$ 表示通过边 $e$ 从顶点 $u$ 移动到顶点 $v$。

在第一个测试用例中，一种可能的解决方案是：

1. 初始时，您在顶点 $1$。
2. 标记边 $3$ 并移动到顶点 $3$，成本为 $6$。
3. 标记边 $6$ 并移动到顶点 $4$，成本为 $7$。
4. 标记边 $1$ 并移动到顶点 $2$，成本为 $15$。
5. 标记边 $4$ 并移动到顶点 $3$，成本为 $9$。
6. 传送到顶点 $5$。通过选择路径 $3 \to 4 \to 2 \to 5$，我们可以实现成本 $7$，因为路径上边的最大索引是 $6$，且 $w_{6}=7$。注意，在使用操作 $2$ 时，我们并不关心路径上的最大权重。
7. 标记边 $2$ 并移动到顶点 $2$，成本为 $4$。
8. 标记边 $5$ 并移动到顶点 $1$，成本为 $10$。

总成本为 $6+7+15+9+7+4+10 = 58$。

在第二个测试用例中，一种可能的解决方案是：

1. 标记边 $1$ 并移动到顶点 $2$，成本为 $3$。
2. 传送到顶点 $3$，通过路径 $2 \to 1 \to 4 \to 1 \to 3$，成本为 $1$。注意操作 $2$ 中选择的路径不必是简单路径。
3. 标记边 $2$ 并移动到顶点 $1$，成本为 $2$。
4. 标记边 $3$ 并移动到顶点 $4$，成本为 $1$。
5. 传送到顶点 $1$，通过路径 $4 \to 1$，成本为 $1$。

数据范围

对于 $40 \%$ 的数据，$n$ 和 $m$ 的总和不超过$10^3$，$0\le w_i \le 1$.

对于 $100 \%$ 的数据，$1 \le t \le 10^4, 1 \le n \le 10^6,0 \le m \le 10^6, 0\le w_i \le 10^9$，保证所描述的图是连通的，同时注意，图中可能存在自环和重边，保证所有测试用例的 $n$ 和 $m$ 的总和分别不超过 $10^{6}$。.