题目背景

此题为 Educational Codeforces Round 3 的 E 题，直接去原网站提交即可。

点我跳转原题

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

给你 $n$ 个点，$m$ 条边的无向简单连通图，如果对于一个最小生成树中要求必须包括第 $i(1 \le i \le m)$ 条边，那么最小生成树的权值总和最小是多少。

输入格式

第一行有两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行有三个整数 $u$，$v$ 和 $w$ 表示一条权值为 $w$ 的边连接 $u$ 和 $v$。

输出格式

总共 $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

说明/提示

$1 \le n \le 2 \times 10^5,n-1 \le m\le 2 \times 10^5$

$1 \le u_i,v_i \le n,u_i \neq v_i,1 \le w_i \le 10^9$