MST Edge Cost

题目描述

给定一个无向加权图，确定对于每条边，如果必须包含该边于生成树中，则最小生成树的代价。

输入格式

第一行有两个整数 n 和 m：节点数和边数。节点编号为 1,2,$\dots$,n。 接下来的 m 行描述边。每行有三个整数 a, b, w：节点 a 和 b 之间有一条权重为 w 的边。 你可以假设图是连通的且简单图，并且每条边在图中最多出现一次。

输出格式

对于输入顺序中的每一条边，输出当该边被包含时的最小生成树代价。

5 6
1 2 4
1 3 2
2 4 2
3 4 1
3 5 4
4 5 3

10
8
8
8
9
8

提示

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$ $1 \le w \le 10^9$

标签: CSES3409|高级图论问题

来源

CSES3409|高级图论问题