問題

ヘビの JOI 君は，ある大きな屋敷に迷い込んでしまった．屋敷の住人に見つかる前に，屋敷を脱出しなければならない．

この屋敷には部屋が N 個あり，1, 2, \ldots, N の番号が付けられている．また，廊下が M 本あり，i 本目の廊下 (1 \leqq i \leqq M) は部屋 A_i と部屋 B_i を結んでいる．JOI 君はこれらの廊下をどちらの向きにも通ることができ，廊下 i を通るのには D_i 分かかる．部屋と部屋の間を廊下を通る以外の手段で移動する方法はない．

この屋敷の部屋の温度はそれぞれ一定に調節されており，JOI 君にとって寒すぎるか，快適であるか，暑すぎるかである．JOI 君は，急な温度変化に対応できないため，最後に寒すぎる部屋を出てから X 分未満のうちに暑すぎる部屋に入ることはできない．同様に，最後に暑すぎる部屋を出てから X 分未満のうちに寒すぎる部屋に入ることもできない．

JOI 君は，移動中に部屋に入るとすぐに部屋から出なければならない．また，廊下の途中で引き返したり，廊下 i を D_i 分より長い時間かけて通ることもできない．ただし，一度訪れた部屋にもう一度入ることや，一度使った廊下をもう一度使うことは許される．

JOI 君は現在部屋 1 にいる．この部屋は JOI 君にとって寒すぎる．JOI 君は屋敷の出口のある部屋 N に入ると，屋敷から脱出できる．

JOI 君が屋敷から脱出するのにかかる最短の時間を求めよ．

入力例 1

8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2

出力例 1

9

入力例 1 では，部屋を 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 5 \rightarrow 8 の順に移動するのが最短となる．

入力例 2

15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1

出力例 2

6

入力例 2 では，いくつかの部屋の組 (たとえば部屋 1 と部屋 5) を結ぶ廊下が複数ある．