Minimum spanning tree for each edge

Description:

Input:

First line contains two integers n and m (1 ≤ n ≤ 2·10⁵, n - 1 ≤ m ≤ 2·10⁵) — the number of vertices and edges in graph.

Each of the next m lines contains three integers u_i, v_i, w_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 10⁹) — the endpoints of the i-th edge and its weight.

Output:

Print m lines. i-th line should contain the minimal possible weight of the spanning tree that contains i-th edge.

The edges are numbered from 1 to m in order of their appearing in input.

Sample Input:

5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4

Sample Output:

9
8
11
8
8
8
9