问题陈述
给你一个无向加权图 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