No.9 ヘビの JOI 君 (Snake JOI)

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

ヘビの 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 行で出力せよ．

入出力例

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

9

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

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

6

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