Problem Description

You are given a simple connected undirected graph with weighted edges, consisting of $ N $ vertices and $ M $ edges. The vertices are numbered from $ 1 $ to $ N $, and the edges are numbered from $ 1 $ to $ M $.

Edge $ i $ connects vertices $ A_i $ and $ B_i $ with a weight of $ C_i $.

For each edge from $ 1 $ to $ M $, determine the minimum weight spanning tree that includes that edge, and output its weight.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ : $ $ A_M $ $ B_M $ $ C_M $

Output Format

Output $ M $ lines. The $ i $-th line should contain the minimum possible weight of a spanning tree that includes edge $ i $.

Sample Input and Output

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

Notes/Hints

Notes

Discussion of this problem is prohibited until May 2, 2020, 18:00 JST. If mentioned, it may lead to claims for compensation.

It is acceptable to publish the total score or certification level after the exam, but please refrain from disseminating information about which problems were solved.

Annotation

• 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 undirected graph is simple and connected.

Sample Explanation 3

Note that the answer may not fit within the range of a 32-bit integer.

见题面 Input 部分

见题面 Output 部分