CF609E.Minimum spanning tree for each edge

Connected undirected weighted graph without self-loops and multiple edges is given. Graph contains n vertices and m edges.

For each edge (u, v) find the minimal possible weight of the spanning tree that contains the edge (u, v).

The weight of the spanning tree is the sum of weights of all edges included in spanning tree.

给定一个无向连通带权图，图中不含自环和重边。该图包含 $n$ 个顶点和 $m$ 条边。

对每条边 $(u,\,v)$，求包含该边 $(u,\,v)$ 的生成树的最小可能权重。

生成树的权重定义为其中所有边的权重之和。

First line contains two integers n and m (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105) — the number of vertices and edges in graph.

Each of the next m lines contains three integers u__i, v__i, w__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i, 1 ≤ w__i ≤ 109) — the endpoints of the i-th edge and its weight.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$，$n - 1 \leq m \leq 2 \cdot 10^5$）—— 分别表示图中的顶点数和边数。

接下来的 $m$ 行中，每行包含三个整数 $u_i,\, v_i,\, w_i$（$1 \leq u_i,\, v_i \leq n$，$u_i \neq v_i$，$1 \leq w_i \leq 10^9$）—— 表示第 $i$ 条边的两个端点及其权重。

Print m lines. i-th line should contain the minimal possible weight of the spanning tree that contains i-th edge.

The edges are numbered from 1 to m in order of their appearing in input.

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

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