This page is still under construction.

Parts of this page are still being built. What you see may change.

Minimum spanning tree after deleting one edge

Time limit3sMemory limit256 MB

Summary
For each edge, report the MST weight of the graph with that edge removed, or -1 when it disconnects.
Level

Medium7 of 10

Topics
Minimum spanning tree, Tree, Union-find
Solved
No attempts yet

Problem

You are given an undirected weighted graph GG with nn nodes and mm edges. The edges are numbered from 11 to mm.

Let GiG_i be the graph obtained by erasing edge ii from GG. For each ii, compute the cost of a minimum spanning tree of GiG_i.

Input

The input has the following format.

n m
a1 b1 w1
...
am bm wm

The first line contains the number of nodes nn and the number of edges mm (2≤n≤100,0002 \le n \le 100{,}000, 1≤m≤200,0001 \le m \le 200{,}000).

Each of the next mm lines contains three integers aia_i, bib_i and wiw_i (1≤ai≤n1 \le a_i \le n, 1≤bi≤n1 \le b_i \le n, 0≤wi≤1,000,0000 \le w_i \le 1{,}000{,}000), the ii-th line describing edge ii: an edge between node aia_i and node bib_i with cost wiw_i.

The graph is guaranteed to be simple. At most one edge connects any pair of nodes, and ai≠bia_i \ne b_i for every ii.

Output

Print mm lines. On line ii, print the cost of a minimum spanning tree of GiG_i. If GiG_i has no spanning tree, print -1 on that line instead.

Examples4

  1. Example 1

    Input
    4 6
1 2 2
1 3 6
1 4 3
2 3 1
2 4 4
3 4 5
    Expected output
    8
6
7
10
6
6

  2. Example 2

    Input
    4 4
1 2 1
1 3 10
2 3 100
3 4 1000
    Expected output
    1110
1101
1011
-1

  3. Example 3

    Input
    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
    Expected output
    27
26
25
29
28
28
28
25
25
25

  4. Example 4

    Input
    3 1
1 3 999
    Expected output
    -1