問題 F - flying snowman

Time Limit: 2 seconds / Memory Limit: 256 MB

問題

今年のクリスマスはサンタさんが忙しいので，雪だるまさんがプレゼント配達の手伝いを行うことになった．現在雪だるまさんは拠点 (番号 0 で表される) にいて，プレゼントを届けたい家が番号 1 から番号 N - 1 までの N - 1 軒ある．

雪だるまさんはこの任務のために特別に翼を授かり，飛んで移動することになったが，飛行にはまだまだ慣れていない．安全のため，飛び始めと飛び終わりは番号 0 から番号 N - 1 までのいずれかの地点でなければならない．2 地点間の飛行にかかる時間は基本的には D 秒であるが，雪だるまさんはいくつかの場所の飛行が苦手であり，各 i (1 ≤ i ≤ M) に対し，地点 A_i から地点 B_i への飛行または地点 B_i から地点 A_i への飛行には C_i 秒かかる．

雪だるまさんは拠点を出発し，N - 1 軒の家を訪れ，また拠点へ戻る．このための飛行時間の合計の最小値を求めたい．なお，各々の家は 1 回以上訪れていれば複数回訪れてもよく，任務の途中で拠点に戻ることも自由である．

入力

N M D
A1 B1 C1
...
AM BM CM

1 行目は 3 つの整数 N, M, D を含む．

続く M 行のうち i 行目 (1 ≤ i ≤ M) は，3 つの整数 A_i, B_i, C_i を含む．

出力

飛行時間の合計の最小値を 1 行に出力せよ．

制約

• 2 ≤ N ≤ 100,000．
• 1 ≤ M ≤ N．
• 1 ≤ D ≤ 10,000．
• 0 ≤ A_i < B_i ≤ N - 1．
• i ≠ j に対し，(A_i, B_i) ≠ (A_j, B_j)．
• D < C_i ≤ 10,000．

部分点

100 点中 25 点分のデータは以下を満たす．

• 2 ≤ N ≤ 15．

入出力例

入力例 1

4 3 10
1 2 40
1 3 20
0 3 50

出力例 1

50

例えば，地点 0, 1, 3, 2, 0 の順に移動するとよい．

入力例 2

4 4 10
1 2 40
1 3 20
0 3 50
2 3 80

出力例 2

80

例えば，地点 0, 1, 3, 1, 0, 2, 0 の順に移動するとよい．

入力例 3

4 1 1
1 3 10000

出力例 3

4

例えば，地点 0, 1, 2, 3, 0 の順に移動するとよい．