最小生成树花费(Minimum Spanning Tree Cost)

题目描述

给定一个包含 $n$ 个顶点、$m$ 条带权无向边的连通图。

对于图中的每一条边 $i$（$1 \le i \le m$），请你求出在必须包含第 $i$ 条边的前提下，原图生成树的最小边权之和。

输入格式

第一行包含两个正整数 $n, m$，分别表示顶点数与边数。

接下来 $m$ 行，每行包含三个正整数 $u_i, v_i, w_i$，表示第 $i$ 条无向边连接顶点 $u_i$ 和 $v_i$，边权为 $w_i$。

输出格式

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

样例输入 #1

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

样例输出 #1

12
12
12
13
15

数据范围

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$n - 1 \le m \le 2 \times 10^5$，$1 \le w_i \le 10^9$，保证图连通。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

测试点分布

出处：原题链接