$(function(){document.getElementById("fixed-server-timer").style.display = "none";})

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

Source Name

Japan Alumni Group Spring Contest 2013