A10090. Minimum spanning tree for each edge

Connected undirected weighted graph without self-loops and multiple edges is given. Graph contains $n$ vertices and $m$ edges.

For each edge $(u,v)$ find the minimal possible weight of the spanning tree that contains the edge $(u,v)$ .

The weight of the spanning tree is the sum of weights of all edges included in spanning tree.

First line contains two integers $n$ and $m$ ( $1<=n<=2·10^{5},n-1<=m<=2·10^{5}$ ) — the number of vertices and edges in graph.

Each of the next $m$ lines contains three integers $u_{i},v_{i},w_{i}$ ( $1<=u_{i},v_{i}<=n,u_{i}≠v_{i},1<=w_{i}<=10^{9}$ ) — the endpoints of the $i$ -th edge and its weight.

Print $m$ lines. $i$ -th line should contain the minimal possible weight of the spanning tree that contains $i$ -th edge.

The edges are numbered from $1$ to $m$ in order of their appearing in input.