10048번 - フクロモモンガ (Sugar Glider) 서브태스크다국어

フクロモモンガの JOI 君が住んでいる森にはユーカリの木が N 本生えており，それらの木には 1 から Nの番号がついている．木 i の高さは Hi メートルである．

JOI 君が相互に直接飛び移ることのできる木の組が M 組あり，各組の木の間を飛び移るためにかかる時間が定まっている．JOI 君が木の間を飛び移っている間は，地面からの高さが 1 秒あたり 1 メートル下がる．すなわち，JOI 君の現在の地面からの高さが h メートル，木の間を飛び移るためにかかる時間が t 秒であるとき，飛び移った後の地面からの高さは h − t メートルとなる．ただし，h − t が 0 よりも小さくなる場合や行き先の木の高さよりも大きくなる場合は飛び移ることができない．

さらに，JOI 君は木の側面を上下に移動することによって，地面からの高さを 0 メートルから今いる木の高さの範囲で増減させることができる．JOI 君が地面からの高さを 1 メートル増加または減少させるためには 1 秒の時間がかかる．

JOI 君は，木 1 の高さ X メートルの位置から木 N の頂上 (高さ H_N メートルの位置) に行こうとしており，そのためにかかる時間の最小値を知りたい．

各木の高さと，JOI 君が直接飛び移ることができる木の組の情報と，最初 JOI 君がいる場所の高さが与えられる．木 N の頂上に行くためにかかる時間の最小値を求めるプログラムを作成せよ.

標準入力から以下のデータを読み込め．

• 1 行目には，整数 N, M, X が空白を区切りとして書かれている．これは，木の本数が N 本，移動できる木の組が M 組あり，最初 JOI 君が木 1 の高さ X メートルの位置にいることを表す．
• 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，整数 H_i が書かれている．これは，木 i の高さが H_i メートルであることを表す．
• 続く M 行のうちの j 行目 (1 ≤ j ≤ M) には，整数 A_j, B_j, T_j (1 ≤ A_j ≤ N, 1 ≤ B_j ≤ N, A_j ≠ B_j) が空白を区切りとして書かれている．これは，木 A_j と木 B_j の間を相互に T_j 秒で飛び移ることができることを表している．また，1 ≤ j < k ≤ M ならば，(A_j, B_j) ≠ (A_k, B_k) および (A_j, B_j) ≠ (B_k, A_k) を満たす．

標準出力に，木 1 の高さ X メートルの位置から木 N の頂上に行くためにかかる時間の最小値を秒単位で表す整数を 1 行で出力せよ．ただし，そのような方法がない場合は代わりに −1 を出力せよ．

• 2 ≤ N ≤ 100 000．
• 1 ≤ M ≤ 300 000．
• 1 ≤ H_i ≤ 1 000 000 000 (1 ≤ i ≤ N)．
• 1 ≤ T_j ≤ 1 000 000 000 (1 ≤ j ≤ M)．
• 0 ≤ X ≤ H₁．

• N ≤ 1 000．
• M ≤ 3 000．
• H_i ≤ 100 (1 ≤ i ≤ N)．
• T_j ≤ 100 (1 ≤ j ≤ M)．

• X = 0．

追加の制限はない．