006 - ヘビの JOI 君 (Snake JOI)

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 2 /


TLE
1sec
MLE
64MB
得点
100

問題

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

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

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

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

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

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

入力

入力は 1 + N + M 行からなる.

1 行目には,3 個の整数 N, M, X (2 ≦ N ≦ 10000, 1 ≦ M ≦ 20000, 1 ≦ X ≦ 200) が空白を区切りとして書かれている.これは,屋敷に N 個の部屋と M 本の廊下があり,JOI 君が温度変化に対応するのに X 分かかることを表す.

続く N 行のうちの i 行目 (1 ≦ i ≦ N) には,部屋 i の温度を表す整数 Ti (0 ≦ Ti ≦ 2) が書かれている.JOI 君にとって部屋 i は,Ti = 0 のとき寒すぎ,Ti = 1 のとき快適であり,Ti = 2 のとき暑すぎる.T1 = 0 であることが保証されている.

続く M 行のうちの j 行目 (1 ≦ j ≦ M) には,3 個の整数 Aj, Bj, Dj (1 ≦ Aj < Bj ≦ N, 1 ≦ Dj ≦ 200) が空白を区切りとして書かれている.これは,廊下 j が部屋 Aj と部屋 Bj を結んでおり,通るのに Dj 分かかることを表す.同じ部屋の組を結ぶ廊下が複数ある可能性があることに注意せよ.

与えられる入力データでは,JOI 君が屋敷から脱出できることは保証されている.

出力

JOI 君が屋敷から脱出するのに最短で何分かかるかを表す整数を 1 行で出力せよ.

入出力例

入力例 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 → 2 → 3 → 4 → 5 → 6 → 5 → 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) を結ぶ廊下が複数ある.