A67213 | 最⼩⽣成树

试题名称：最⼩⽣成树

时间限制： 1.0 s

内存限制：512.0 MB

3.2.1     题目描述

给定一张包含 n 个结点 m 条边的带权连通⽆向图 ，结点依次以1 , 2,  ....., n 编号  ，第 i 条边（ 1 ≤ i ≤ m）连接结点 u_i与结点 v_i ，边权为 w_i 。

对于每条边 ，请你求出从图中移除该条边后 ，图的最⼩⽣成树中所有边的边权和 。特别地 ，若移除某条边后图的最⼩⽣成树不存在 ，则输出1 。

3.2.2     输入格式

第一⾏ ，两个正整数 n, m ，分别表⽰图的结点数与边数。

接下来 m ⾏中的第 i ⾏（ 1 ≤ i ≤ m） 包含三个正整数 u_i , v_i,wi ，表⽰图中连接结点 u_i 与结点 v_i 的边 ，边权为 w_i 。

3.2.3     输出格式

输出共 m ⾏ ，第 i ⾏（ 1 ≤ i ≤ m）包含一个整数 ，表⽰移除第 i 条边后 ，图的最⼩⽣成树中所有边的边权和 。若移 除第 i 条边后图的最⼩⽣成树不存在 ，则输出   1 。

3.2.4     样例

3.2.4.1     输入样例 1

5  5

1  2  4

2  3  3

3  4  1

2  5  2

3  1  8

3.2.4.2     输出样例 1

14

15

-1

-1

10

3.2.4.3     输入样例 2

6  10

1  2  6

2  3  3

3  1  4

3  4  5

4  5  8

5  6  2

6  4  1

3  2  4

5  4  4

3  3  6

3.2.4.4     输出样例 2

15

16

17

-1

15

17

18

15

15

15

3.2.5     数据范围