CF2164E Journey

你现在处于一个包含 $n$ 个顶点和 $m$ 条带权无向边的连通图上，所有边从 $1$ 到 $m$ 编号。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$ ，权值为 $w_i$ 。你决定在图上开始一次美妙的旅行。 假设你现在在顶点 $x$ ，你可以进行任意多次如下操作： 1. 标记一条连接 $x$ 和 $y$ 的边，沿着该边拍照，并移动到 $y$ ，花费为该边的权值。 2. 乘坐火车传送到任意另一个顶点 $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}$，且对所有 $i \in [1,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$ 行，每行三个整数 $u_i, v_i, w_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$），表示编号为 $i$ 的边连接 $u_i$ 与 $v_i$，权值为 $w_i$。 保证图是连通的。 图中可能存在自环和重边。 保证所有测试用例中 $n$ 与 $m$ 的总和分别不超过 $10^6$。

对于每个测试用例输出一个整数，表示最小花费。

[可视化链接](https://codeforces.com/assets/contests/2164/E_ooxathoosh9Oob4quoiv.html) 用 $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 \xrightarrow{6} 4 \xrightarrow{1} 2 \xrightarrow{2} 5$，因该路径上最大编号为 $6$，且 $w_6 = 7$，花费 $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 \xrightarrow{1} 1 \xrightarrow{3} 4 \xrightarrow{3} 1 \xrightarrow{2} 3$，最大编号为 $3$，$w_3=1$，花费 $1$。注意操作 2 允许路径不是简单路径。 3. 标记第 $2$ 条边并移动到顶点 $1$，花费 $2$。 4. 标记第 $3$ 条边并移动到顶点 $4$，花费 $1$。 5. 传送到顶点 $1$，路径 $4 \xrightarrow{3} 1$，花费 $1$。 由 ChatGPT 5 翻译