Time Limit: 10 sec / Memory Limit: 256 MB
配点: 100 点
問題
ヘビの 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 + N + M 行からなる.
1 行目には,3 個の整数 N, M, X (2 \leqq N \leqq 10\,000,1 \leqq M \leqq 20\,000,1 \leqq X \leqq 200) が空白を区切りとして書かれている.これは,屋敷に N 個の部屋と M 本の廊下があり,JOI 君が温度変化に対応するのに X 分かかることを表す.
続く N 行のうちの i 行目 (1 \leqq i \leqq N) には,部屋 i の温度を表す整数 T_i (0 \leqq T_i \leqq 2) が書かれている.JOI 君にとって部屋 i は,T_i = 0 のとき寒すぎ,T_i = 1 のとき快適であり,T_i = 2 のとき暑すぎる.T_1 = 0 であることが保証されている.
続く M 行のうちの j 行目 (1 \leqq j \leqq M) には,3 個の整数 A_j, B_j, D_j (1 \leqq A_j < B_j \leqq N,1 \leqq D_j \leqq 200) が空白を区切りとして書かれている.これは,廊下 j が部屋 A_j と部屋 B_j を結んでおり,通るのに D_j 分かかることを表す.同じ部屋の組を結ぶ廊下が複数ある可能性があることに注意せよ.
与えられる入力データでは,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 \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) を結ぶ廊下が複数ある.