E - Minimum Spanning Tree

Problem Statement

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

Let G_i 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 G_i for each i.

Input

The dataset is formatted as follows.

n m
a_1 b_1 w_1
...
a_m b_m w_m

The first line of the input contains two integers $n (2 \leq n \leq 100{,}000)$ and $m (1 \leq m \leq 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 $a_i (1 \leq a_i \leq n), b_i (1 \leq b_i \leq n)$ and $w_i (0 \leq w_i \leq 1{,}000{,}000)$. This means that there is an edge between node a_i and node b_i and its cost is w_i. 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 $a_i \neq b_i$ for all i.

Output

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

Sample Input 1

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

Output for the Sample Input 1

8
6
7
10
6
6

Sample Input 2

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

Output for the Sample Input 2

1110
1101
1011
-1

Sample Input 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

Output for the Sample Input 3

27
26
25
29
28
28
28
25
25
25

Sample Input 4

3 1
1 3 999

Output for the Sample Input 4

-1

Example

Input

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

Output

8
6
7
10
6
6

见题面

见题面