← 返回题目列表

Codeforces · 609/E

E. 每条边的最小生成树

中文机器翻译题面 查看原题

给出了无自环和多边的连通无向加权图。图包含 n 个顶点和 m 个边。

对于每条边 (u, v),找到包含边 (u, v) 的生成树的最小可能权重。

生成树的权重是生成树中包含的所有边的权重之和。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105) — 图中的顶点和边的数量。

接下来的 m 行中的每一行都包含三个整数 ui, vi, wi (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 109) — 第 i 条边的端点及其权重。

输出

打印 m 行。第 i 行应包含包含第 i 条边的生成树的最小可能权重。

边按照其在输入中出现的顺序从 1 到 m 编号。

示例

输入 #1

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

输出 #1

9
8
11
8
8
8
9