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 公園の整備にかかるコストの和の最小値を求めるプログラムを作成せよ．

制限

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

• 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 点]

追加の制限はない．

入力例 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 \times 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 としてすべての広場を相互に地下道で結んだとき，整備にかかるコストの和が最小になる．