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`.

The dataset is formatted as follows.

nma_1b_1w_1...a_mb_mw_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`.

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.

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

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

1110 1101 1011 -1

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

27 26 25 29 28 28 28 25 25 25

3 1 1 3 999

-1

Source: Japan Alumni Group Spring Contest 2013
, Japan, 2013-04-21

http://acm-icpc.aitea.net/

http://jag2013spring.contest.atcoder.jp/

http://acm-icpc.aitea.net/

http://jag2013spring.contest.atcoder.jp/