← 返回题目列表

AtCoder · icpc2013spring_e

E. 最小生成树

中文机器翻译题面 查看原题

问题陈述

给你一个无向加权图 G 与 n 节点和 m 边缘。 每条边的编号从 1 to m.

让 G_i 是通过擦除得到的图形 i从第一个边缘 G。你的任务是计算最小生成树的成本 G_i 对于每个 i.


输入

数据集的格式如下。

n m
a_1 b_1 w_1
...
a_m b_m w_m

输入的第一行包含两个整数 n (2 \leq n \leq 100{,}000)和 m (1 \leq m \leq 200{,}000). n 是节点数, m 是图中的边数。 然后 m 行如下,每行包含 a_i (1 \leq a_i \leq n), b_i (1 \leq b_i \leq n)和 w_i (0 \leq w_i \leq 1{,}000{,}000)。 这意味着节点之间存在边 a_i 和节点 b_i 其成本是 w_i。 保证给定的图是简单的:即对于任意一对节点,最多有一条边连接它们,并且 a_i \neq b_i 对于所有人 i.

输出

打印最小生成树的成本 G_i 对于每个 i,在 m 线。如果没有生成树 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