ヘビの JOI 君 (Snake JOI)

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

この屋敷には部屋が N 個あり,1, 2, ..., N の番号が付けられている.また,廊下が M 本あり,i 本目の廊下 (1 ≦ i ≦ 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 ≦ N ≦ 10000, 1 ≦ M ≦ 20000, 1 ≦ X ≦ 200) が空白を区切りとして書かれている.これは,屋敷に N 個の部屋と M 本の廊下があり,JOI 君が温度変化に対応するのに X 分かかることを表す.

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

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

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

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

생성자가 기록되지 않았습니다.

출처 JOI 2017 Preliminary