AT_joi2015ho_c JOI 公園 (JOI Park)

[problemUrl]: https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_c 20XX 年に IOI 国で行われるオリンピックに備え，IOI 国にある JOI 公園を整備することになった．JOI公園には $ N $ 個の広場があり，広場には $ 1 $ から $ N $ の番号がついている．広場を繋ぐ $ M $ 本の道があり，道には $ 1 $ から $ M $ の番号がついている．道 $ i $ ($ 1\ \leqq\ i\ \leqq\ M $) は広場 $ A_i $ と広場 $ B_i $ を双方向に繋いでおり，長さは $ D_i $ である．どの広場からどの広場へもいくつかの道を辿って行くことができる． 整備計画では，まず，$ 0 $ 以上の整数 $ X $ を選び，広場 $ 1 $ からの距離が $ X $ 以下であるような広場 (広場 $ 1 $ を含む) どうしをすべて相互に地下道で結ぶ．ただし，広場 $ i $ と広場 $ j $ の距離とは，広場 $ i $ から広場 $ j $ に行くときに通る道の長さの和の最小値である．整備計画では地下道の整備コストに関する整数 $ C $ が定まっている．地下道の整備にかかるコストは $ C\ \times\ X $ である． 次に，地下道で結ばれた広場どうしを結ぶ道をすべて撤去する．道の撤去にコストはかからない． 最後に，撤去されずに残った道をすべて補修する．長さ $ d $ の道を補修するためにかかるコストは $ d $ である． 整備計画実施前の JOI 公園には地下道はない．JOI 公園の整備にかかるコストの和の最小値を求めよ．

N/A

N/A

### 課題 JOI 公園の広場の情報と，地下道の整備コストに関する整数が与えられたとき，JOI 公園の整備にかかるコストの和の最小値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 2\ \leqq\ N\ \leqq\ 100\,000 $． - $ 1\ \leqq\ M\ \leqq\ 200\,000 $． - $ 1\ \leqq\ C\ \leqq\ 100\,000 $． - $ 1\ \leqq\ A_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ 1\ \leqq\ B_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ A_i\ \neq\ B_i $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ (A_i,\ B_i)\ \neq\ (A_j,\ B_j) $ および $ (A_i,\ B_i)\ \neq\ (B_j,\ A_j) $ ($ 1\ \leqq\ i\