JOI 公園 (JOI Park)

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 公園の整備にかかるコストの和の最小値を求めよ．

課題

JOI 公園の広場の情報と，地下道の整備コストに関する整数が与えられたとき，JOI 公園の整備にかかるコストの和の最小値を求めるプログラムを作成せよ．

標準入力から以下のデータを読み込め．

• \(1\) 行目には，整数 \(N, M, C\) が空白を区切りとして書かれている．これは，広場が \(N\) 個，道が \(M\) 本あり，地下道の整備コストに関する整数が \(C\) であることを表す．
• 続く \(M\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq M\)) には，整数 \(A_i, B_i, D_i\) が空白を区切りとして書かれている．これは，道 \(i\) が広場 \(A_i\) と広場 \(B_i\) を繋ぎ，長さが \(D_i\) であることを表す．

標準出力に，JOI 公園の整備にかかるコストの和の最小値を表す整数を \(1\) 行で出力せよ．

すべての入力データは以下の条件を満たす．

• \(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 < j \leqq M\))．
• \(1 \leqq D_i \leqq 100\,000\) (\(1 \leqq i \leqq M\))．
• 与えられる入力データにおいては，どの広場からどの広場へもいくつかの道を辿ることにより行けることが保証されている．

小課題 1 [15 点]

以下の条件を満たす．

• \(N \leqq 100\)．
• \(M \leqq 200\)．
• \(C \leqq 100\)．
• \(D_i \leqq 10\) (\(1 \leqq i \leqq M\))．

小課題 2 [45 点]

以下の条件を満たす．

• \(N \leqq 100\)．
• \(M \leqq 4\,000\)．

小課題 3 [40 点]

追加の制限はない．

JOI 2015 · JCIOI · CC BY-SA 4.0