A16757. Journey
编程题
省选/NOI-
知识点
题目描述
你现在处于一个包含 $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$。请计算最小花费。
请注意，传送的花费不是路径上的最大边权，也不是最大编号本身。如果有疑问可参考下方说明。
假设你现在在顶点 $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$。
每个测试用例的第一行为两个整数 $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$。
输出格式
对于每个测试用例输出一个整数，表示最小花费。
输入输出样例
输入 #1
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
输出 #1
58 8 8 71 43
说明/提示
[可视化链接](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$。
用 $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$。