AT_joi2017yo_f ヘビの JOI 君 (Snake JOI)

[problemUrl]: https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_f ヘビの 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\

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

### Sample Explanation 1 入力例 $ 1 $ では，部屋を $ 1\ \rightarrow\ 2\ \rightarrow\ 3\ \rightarrow\ 4\ \rightarrow\ 5\ \rightarrow\ 6\ \rightarrow\ 5\ \rightarrow\ 8 $ の順に移動するのが最短となる． - - - - - - ### Sample Explanation 2 入力例 $ 2 $ では，いくつかの部屋の組 (たとえば部屋 $ 1 $ と部屋 $ 5 $) を結ぶ廊下が複数ある．