0273 - フクロモモンガ (Sugar Glider)

問題

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

小課題

小課題 1 [25 点]

　以下の条件を満たす．

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

小課題 2 [25 点]

　以下の条件を満たす．

• X = 0．

小課題 3 [50 点]

　追加の制限はない．

入出力例

入力例 1

5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20

出力例 1

110

　例えば，以下のように移動すればよい．

1. 木 1 を 50 メートル登る．
2. 木 1 から木 2 に飛び移る．
3. 木 2 から木 4 に飛び移る．
4. 木 4 から木 5 に飛び移る．
5. 木 5 を 10 メートル登る．

入力例 2

2 1 0
1
1
1 2 100

出力例 2

-1

　JOI 君は木 1 から木 2 に飛び移ることができない．

入力例 3

4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10

出力例 3

100