Minimum spanning tree for each edge

题目来源

CF 609E

题目描述

给定一张 $n$ 个顶点 $m$ 条边的带权无向简单图，顶点编号从 $1$ 到 $n$，对于每一条边请求出包含这条边的生成树的最小边权和。

输入格式

第一行两个数 $n,m$，表示顶点数和边数。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示 $u$ 号点和 $v$ 号点之间有一条边权为 $w$ 的边。

输出格式

输出共 $m$ 行，第 $i$ 行一个整数表示包含第 $i$ 条边的生成树的最小边权和。

样例输入

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

样例输出

9
8
11
8
8
8
9

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 2×10^5, n-1\leq m\leq 2×10^5, 1\leq u, v\leq n, 1\leq w\leq 10^9$，数据保证图连通。