最⼩⽣成树

题目描述

给定⼀张包含 个结点 条边的带权连通⽆向图，结点依次以 编号，第 条边（ ）连接结点 与结点 ，边权为 。 对于每条边，请你求出从图中移除该条边后，图的最⼩⽣成树中所有边的边权和。特别地，若移除某条边后图的最 ⼩⽣成树不存在，则输出 。

输入格式

第⼀⾏，两个正整数 ，分别表⽰图的结点数与边数。 接下来 ⾏中的第 ⾏（ ）包含三个正整数 ，表⽰图中连接结点 与结点 的边，边权为 。

输出格式

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

样例输入 #1

5 5
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8

样例输出 #1

14
15
-1
-1
10

样例输入 #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 % - 对于所有测试点，保证 ， ， ， 。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。