AT_past202004_o 可変全域木

给定一张 $n$ 点（编号 $1$ 到 $n$）$m$ 边（编号 $1$ 到 $m$）的简单联通无向图，边 $i$ 连接顶点 $a_i$ 和 $b_i$，边权为 $c_i$。 对于从 $1$ 到 $m$ 的每条边，找出包含该边且权重最小的生成树，并输出其权重（输入输出样例 #3 证明了结果可能会爆`int`）。

第一行：$n,m$ 接下来 $m$ 行：第 $i$ 行为 $a_i,b_i,c_i$

$m$ 行，第 $i$ 行输出包含边 $i$ 的最小权重生成树的权重。 ### 约束 $2 \le n\le 10^5$ $n-1 \le m \le \min(10^5,n(n-1)/2)$ $1 \le a_i,b_i \le n$ $a_i \neq b_i$ $1 \le c_i \le 10^9$

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 注釈 - 連結無向グラフ $ (V,\ E) $ における**全域木**とは、ある辺の部分集合 $ T\ \subseteq\ E $ について $ (V,\ T) $ と書ける木のことである。 - 全域木 $ (V,\ T) $ の重みは、$ T $ に含まれる全ての辺の重みの和である。 ### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ N\ -\ 1\ \leq\ M\ \leq\ \mathrm{min}(10^5,\ N(N\ -\ 1)/2) $ - $ 1\ \leq\ A_i,\ B_i\ \leq\ N $ ($ 1\ \leq\ i\ \leq\ M $) - $ A_i\ \neq\ B_i $ ($ 1\ \leq\ i\ \leq\ M $) - $ 1\ \leq\ C_i\ \leq\ 10^9 $ ($ 1\ \leq\ i\ \leq\ M $) - 与えられる無向グラフは単純かつ連結である ### Sample Explanation 3 答えが 32 ビット整数の範囲内でないこともあるため、注意してください。