← 返回题目列表

AtCoder · past202004_o

O. 变量生成树

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

分数: 6 点

警告

2020 年 5 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。

考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。

问题陈述

给定一个简单连通的无向图,其 N 顶点和 M 边缘。顶点已编号 1 to N,并且边缘已编号 1 to M.

边缘 i 连接顶点 A_i 和 B_i,并且该边的权重为 C_i.

对于每一条从 1 to M的边,找到包含该边的最小权重生成树,并打印该树的权重。

注释

  • A 生成树 在一个连通的无向图中 (V, E) 是一棵树,可以写成 (V, T) 对于某些边的子集 T \subseteq E.
  • 生成树的权重 (V, T) 是所有边的权重之和 T.

约束

  • 2 \leq N \leq 10^5
  • N - 1 \leq M \leq \mathrm{min}(10^5, N(N - 1)/2)
  • 1 \leq A_i, B_i \leq N (1 \leq i \leq M)
  • A_i \neq B_i (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • 给定的图很简单且连通。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1 C_1
:
A_M B_M C_M

输出

打印 M 行。的 i- 行应包含包含该边的生成树的最小可能权重 i.


示例输入 1

3 3
1 2 2
2 3 5
3 1 3

示例输出 1

5
7
5

示例输入 2

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

示例输出 2

20
21
19
19
19
21
19

示例输入 3

8 10
1 2 314159265
2 3 358979323
3 4 846264338
1 3 327950288
1 4 419716939
2 4 937510582
1 5 97494459
1 6 230781640
1 7 628620899
1 8 862803482

示例输出 3

2881526972
2912556007
3308074371
2881526972
2881526972
3399320615
2881526972
2881526972
2881526972
2881526972

请注意,答案可能不适合 32 位整数类型。