問題 F - flying snowman

Time Limit: 2 seconds / Memory Limit: 256 MB

問題

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

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

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

入力

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

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

続く M 行のうち i 行目 (1 ≤ iM) は,3 つの整数 Ai, Bi, Ci を含む.

出力

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

制約

部分点

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

入出力例

入力例 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 の順に移動するとよい.


Problem Setter: hos