Minimum Spanning Tree

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

inputFormat

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.

outputFormat

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

样例

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

8
6
7
10
6
6

</p>