#### Registered Users Only

Please login to view and utilize this feature.

## 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 *i*th power line connects town *A _{i}* and

*B*, and costs

_{i}*C*

_{i}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 *i*th power line, what is the minimum possible total cost of the remaining power lines if he keeps the *i*th 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, *A _{i}*,

*B*and

_{i}*C*.

_{i}## Output

The *i*th line should contain one integer, the minimum possible total cost of the remaining power lines if the *i*th power line is part of the remaining power lines.

## Limits

For all subtasks, 1 ≤ *A _{i}*,

*B*≤

_{i}*N*. 1 ≤

*C*≤ 10

_{i}^{9}.

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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 37 | 30 | 1s | 256MB | Minimum |

2 | 63 | 40 | 1s | 256MB | Minimum |

3 | 0 | 1 | 1s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o powergrid -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512