题目描述
给定一张 n 个点、m 条边的连通带权无向图,点编号为 1 到 n,边按输入顺序编号为 1 到 m。
对每条边 i,求:在所有包含边 i 的生成树中,边权和的最小值。
输入格式
第一行两个整数 n、m。
接下来 m 行,每行三个整数 ui、vi、wi,表示第 i 条边连接 ui 和 vi,边权为 wi。
输出格式
输出 m 行,第 i 行一个整数,表示包含第 i 条边的最小生成树的边权和。
样例
5 7
1 2 1
1 3 1
2 3 1
3 4 1
3 5 1
4 5 1
1 5 2
4
4
4
4
4
4
5
4 5
1 2 2
2 3 3
3 4 1
1 3 5
2 4 4
6
6
6
8
7
样例解释
第一组样例中,前六条边可以组成一棵权值和为 4 的最小生成树,包含其中任意一条时答案都是 4。最后一条边 (1,5,2) 加入后,需要换掉树上 1 到 5 路径中权值最大的一条边,答案为 4+2−1=5。
第二组样例中,最小生成树是 (1,2,2)、(2,3,3)、(3,4,1),权值和为 6。第 4 条边 (1,3,5) 加入后,路径最大边为 3,答案为 6+5−3=8;第 5 条边 (2,4,4) 加入后,路径最大边为 3,答案为 6+4−3=7。
数据范围与约定
| 子任务 |
分值 |
限制 |
| 1 |
30 |
2≤n≤100,n−1≤m≤100 |
| 2 |
2≤n≤2000,n−1≤m≤2000 |
| 3 |
40 |
2≤n≤2×105,n−1≤m≤2×105,1≤wi≤109 |
图保证连通,1≤ui=vi≤n,1≤wi≤109。