AT_past202004_o 可変全域木

[problemUrl]: https://atcoder.jp/contests/past202004-open/tasks/past202004_o $ N $ 頂点 $ M $ 辺の重みつき単純連結無向グラフが与えられます。頂点には $ 1 $ から $ N $、辺には $ 1 $ から $ M $ までの番号が振られています。 辺 $ i $ は頂点 $ A_i $ と $ B_i $ を結び、その重みは $ C_i $ です。 辺 $ 1 $ から辺 $ M $ までのそれぞれの辺について、その辺を含む最小の重みの全域木を求め、その重みを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ : $ $ A_M $ $ B_M $ $ C_M $

$ M $ 行出力せよ。$ i $ 行目には、辺 $ i $ を含む全域木の重みとしてありえる最小値を出力せよ。

### 注意 この問題に対する言及は、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 ビット整数の範囲内でないこともあるため、注意してください。