时间限制：1000 ms
内存限制：512 MiB
标准输入输出
题目类型：传统
评测方式：文本比较
给定一张包含 个结点 条边的带权连通无向图，结点依次以 编号，第 条边（）连接结点 与结点 ，边权为 。
对于每条边，请你求出从图中移除该条边后，图的最小生成树中所有边的边权和。特别地，若移除某条边后图的最小生成树不存在，则输出 。
第一行，两个正整数 ，分别表示图的结点数与边数。
接下来 行中的第 行（）包含三个正整数 ，表示图中连接结点 与结点 的边，边权为 。
输出共 行，第 行（）包含一个整数，表示移除第 条边后，图的最小生成树中所有边的边权和。若移除第 条边后图的最小生成树不存在，则输出 。
样例输入 1
5 5
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8
样例输出 1
样例输入 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
样例输出 2
15
16
17
-1
15
17
18
15
15
15
| 子任务编号 |
测试点占比 |
|
|
特殊性质 |
| 1 |
|
|
|
- |
| 2 |
|
|
|
| 3 |
|
|
- |
| 4 |
|
|
对于所有测试点，保证 ，，，。