最小生成树

题目描述

给定一张包含 (n) 个结点 (m) 条边的带权连通无向图，结点依次以 (1, 2, \dots, n) 编号。第 (i) 条边连接结点 (u_i) 与结点 (v_i)，边权为 (w_i)。

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

输入格式

第一行，两个正整数 (n, m)，分别表示图的结点数与边数。 接下来 (m) 行中的第 (i) 行包含三个正整数 (u_i, v_i, w_i)，表示图中连接结点 (u_i) 与结点 (v_i) 的边，边权为 (w_i)。

输出格式

输出共 (m) 行，第 (i) 行包含一个整数，表示移除第 (i) 条边后，图的最小生成树中所有边的边权和。若移除第 (i) 条边后图的最小生成树不存在，则输出 (-1)。

样例

输入样例 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 \le n \le 10^5)，(n-1 \le m \le 2 \times 10^5)，(1 \le w_i \le 10^6)。

注：原始 PDF 因字体原因丢失了数据范围里的数字，此处重建为 (2 \le n \le 10^5)，(n-1 \le m \le 2 \times 10^5)，(1 \le w_i \le 10^6)。测试数据使用了较小的 (n, m) 以保证校验稳定；官方参考程序同样能正确求解。