Problem Description
Damian is now managing the power grid for his district of N towns numbered 1 to N. There are M power lines in his power grid numbered 1 to M. Each power line connects two towns, the ith power line connects town Ai and Bi, and costs Ci
FanPu has just taken presidency of the district and has ordered Damian to cut down on the number of power lines in order to Make District Great Again. He wants Damian to remove power lines in some way such that only N - 1 power lines remain, and that all towns must still be connected to one another directly or indirectly via power lines after the removal.
Damian now wants to know, for the ith power line, what is the minimum possible total cost of the remaining power lines if he keeps the ith power line as part of the remaining power lines in the power grid.
Damian wants to know the above for each of the M power lines. Please help him.
Input
The first line of input will contain two integers, N and M
The next M lines of input will contain three integers each, Ai, Bi and Ci.
Output
The ith line should contain one integer, the minimum possible total cost of the remaining power lines if the ith power line is part of the remaining power lines.
Limits
For all subtasks, 1 ≤ Ai, Bi ≤ N. 1 ≤ Ci ≤ 109.
Subtask 1 (37%): 2 ≤ N ≤ 500. N - 1 ≤ M ≤ 1000.
Subtask 2 (63%): 2 ≤ N ≤ 200 000. N - 1 ≤ M ≤ 400 000.
Subtask 3 (0%): Sample Testcases
Sample Testcase 1
Input
5 7
2 3 3
2 4 1
2 5 5
3 4 2
3 1 3
4 5 2
5 1 4
Output
9
8
11
8
8
8
9