A10090 | $Minimum spanning tree for each edge$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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.

输入 #1

输出 #1

C++ 编辑器

输入

输出