给出了无自环和多边的连通无向加权图。图包含 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