Minimum Spanning Tree for Each Edge

Problem Background

CF 609E

Problem Description

Given an undirected weighted simple graph with $n$ vertices and $m$ edges, with vertices numbered from $1$ to $n$, for each edge compute the minimum total weight of a spanning tree that contains this edge.

Input Format

The first line contains two integers $n, m$, the number of vertices and edges.

The next $m$ lines each contain three integers $u, v, w$, meaning there is an edge of weight $w$ between vertex $u$ and vertex $v$.

Output Format

Output $m$ lines in total; the $i$-th line contains one integer, the minimum total weight of a spanning tree containing the $i$-th edge.

Sample Input

5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4

Sample Output

9
8
11
8
8
8
9

Constraints

For $100\%$ of the data: $1 \leq n \leq 2\times 10^5$, $n-1 \leq m \leq 2\times 10^5$, $1 \leq u, v \leq n$, $1 \leq w \leq 10^9$. The graph is guaranteed to be connected.