题目描述

给定一个具有 n 个节点和 m 条边的无向加权图 G。每条边从 1 到 m 进行编号。

设 G_i 是通过从 G 中删除第 i 条边得到的图。你的任务是计算每个 i 中 G_i 的最小生成树的代价。

输入

输入数据集的格式如下。

n m a_1 b_1 w_1 ... a_m b_m w_m

输入的第一行包含两个整数 n 和 m。其中 n（$2 \leq n \leq 100,000$）是节点数，m（$1 \leq m \leq 200,000$）是图中的边数。然后是 m 行，每行包含三个整数 a_i、b_i 和 w_i。此表示节点 a_i 和节点 b_i 之间存在一条边，其权重为 w_i。保证给定的图是简单图：也就是说，对于任意一对节点，最多只有一条连接它们的边，并且对于所有 i，a_i 不等于 b_i。

输出

对于每个 i，在一行中输出 G_i 的最小生成树的代价。如果 G_i 中不存在生成树，则输出 "-1"。

示例输入1

4 6
1 2 2
1 3 6
1 4 3
2 3 1
2 4 4
3 4 5

示例输出1

8
6
7
10
6
6

示例输入2

4 4
1 2 1
1 3 10
2 3 100
3 4 1000

示例输出2

1110
1101
1011
-1

示例输入3

7 10
1 2 1
1 3 2
2 3 3
2 4 4
2 5 5
3 6 6
3 7 7
4 5 8
5 6 9
6 7 10

示例输出3

27
26
25
29
28
28
28
25
25
25

示例输入4

3 1
1 3 999

示例输出4

-1

来源

日本校友团春季竞赛2013