分数: 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 位整数类型。