002 - JOI公園

問題

20XX 年に IOI 国で行われるオリンピックに備え，IOI 国にある JOI 公園を整備することになった．JOI公園には N 個の広場があり，広場には 1 から N の番号がついている．広場を繋ぐ M 本の道があり，道には 1 から M の番号がついている．道 i (1 ≤ i ≤ M) は広場 A_i と広場 B_i を双方向に繋いでおり，長さは D_i である．どの広場からどの広場へもいくつかの道を辿って行くことができる．

整備計画では，まず，0 以上の整数 X を選び，広場 1 からの距離が X 以下であるような広場 (広場 1 を含む) どうしをすべて相互に地下道で結ぶ．ただし，広場 i と広場 j の距離とは，広場 i から広場 j に行くときに通る道の長さの和の最小値である．整備計画では地下道の整備コストに関する整数 C が定まっている．地下道の整備にかかるコストは C × X である．

次に，地下道で結ばれた広場どうしを結ぶ道をすべて撤去する．道の撤去にコストはかからない．最後に，撤去されずに残った道をすべて補修する．長さ d の道を補修するためにかかるコストは d である．整備計画実施前の JOI 公園には地下道はない．JOI 公園の整備にかかるコストの和の最小値を求めよ．

課題

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

入力

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

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

出力

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

制限

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

• 2 ≤ N ≤ 100 000．
• 1 ≤ M ≤ 200 000．
• 1 ≤ C ≤ 100 000．
• 1 ≤ A_i ≤ N (1 ≤ i ≤ M)．
• 1 ≤ B_i ≤ N (1 ≤ i ≤ M)．
• A_i ≠ B_i (1 ≤ i ≤ M)．
• (A_i, B_i) ≠ (A_j, B_j) および (A_i, B_i) ≠ (B_j, A_j) (1 ≤ i < j ≤ M)．
• 1 ≤ D_i ≤ 100 000 (1 ≤ i ≤ M)．
• 与えられる入力データにおいては，どの広場からどの広場へもいくつかの道を辿ることにより行けることが保証されている．

入出力例

入力例 1

5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5

出力例 1

14

この入力例では，X = 3 として，広場 1 からの距離が 3 以下であるような広場 (広場 1, 広場 2, 広場 3) どうしをすべて相互に地下道で結んだとき，整備にかかるコストの和は 2 × 3 + 3 + 5 = 14 となる．これが最小値である．

入力例 2

5 4 10
1 2 3
2 3 4
3 4 3
4 5 5

出力例 2

15

この入力例では，X = 0 のとき整備にかかるコストの和が最小になる．

入力例 3

6 5 2
1 2 2
1 3 4
1 4 3
1 5 1
1 6 5

出力例 3

10

この入力例では，X = 5 としてすべての広場を相互に地下道で結んだとき，整備にかかるコストの和が最小になる．