시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB66723016934.702%

문제

You are given an undirected weighted graph G with n nodes and m edges. Each edge is numbered from 1 to m.

Let Gi be an graph that is made by erasing i-th edge from G. Your task is to compute the cost of minimum spanning tree in Gi for each i.

입력

The dataset is formatted as follows.

n m
a1 b1 w1
...
am bm wm

The first line of the input contains two integers n (2 ≤ n ≤ 100,000) and m (1 ≤ m ≤ 200,000). n is the number of nodes and m is the number of edges in the graph. Then m lines follow, each of which contains ai (1 ≤ ai ≤ n), bi (1 ≤ bi ≤ n) and wi (0 ≤ wi ≤ 1,000,000). This means that there is an edge between node ai and node bi and its cost is wi. It is guaranteed that the given graph is simple: That is, for any pair of nodes, there is at most one edge that connects them, and ai ≠ bi for all i.

출력

Print the cost of minimum spanning tree in Gi for each i, in m line. If there is no spanning trees in Gi, print "-1" (quotes for clarity) instead.

예제 입력 1

4 6
1 2 2
1 3 6
1 4 3
2 3 1
2 4 4
3 4 5

예제 출력 1

8
6
7
10
6
6

예제 입력 2

4 4
1 2 1
1 3 10
2 3 100
3 4 1000

예제 출력 2

1110
1101
1011
-1

예제 입력 3

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

예제 출력 3

27
26
25
29
28
28
28
25
25
25

예제 입력 4

3 1
1 3 999

예제 출력 4

-1