O - Variable Spanning Trees Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

N 頂点 M 辺の重みつき単純連結無向グラフが与えられます。頂点には 1 から N、辺には 1 から M までの番号が振られています。

辺 i は頂点 A_i と B_i を結び、その重みは C_i です。

辺 1 から辺 M までのそれぞれの辺について、その辺を含む最小の重みの全域木を求め、その重みを出力してください。

注釈

  • 連結無向グラフ (V, E) における全域木とは、ある辺の部分集合 T \subseteq E について (V, T) と書ける木のことである。
  • 全域木 (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 ビット整数の範囲内でないこともあるため、注意してください。

Score : 6 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a simple connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the edges are numbered 1 to M.

Edge i connects Vertex A_i and B_i, and the weight of this edge is C_i.

For each edge from 1 to M, find a minimum-weight spanning tree containing that edge, and print the weight of that tree.

Notes

  • A spanning tree in a connected undirected graph (V, E) is a tree that can be written as (V, T) for some subset of edges T \subseteq E.
  • The weight of a spanning tree (V, T) is the sum of the weights of all edges in T.

Constraints

  • 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)
  • The given graph is simple and connected.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
:
A_M B_M C_M

Output

Print M lines. The i-th line should contain the minimum possible weight of a spanning tree containing Edge i.

Sample Input 1

3 3
1 2 2
2 3 5
3 1 3

Sample Output 1

5
7
5

Sample Input 2

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

Sample Output 2

20
21
19
19
19
21
19

Sample Input 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

Sample Output 3

2881526972
2912556007
3308074371
2881526972
2881526972
3399320615
2881526972
2881526972
2881526972
2881526972

Note that the answer may not fit into a 32-bit integer type.