フクロモモンガ(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 \leq i \leq N)$ には，整数 $H_i$ が書かれている．これは，木 $i$ の高さが $H_i$ メートルであることを表す．
• 続く$M$ 行のうちの $j$ 行目$(1 \leq j \leq M)$ には，整数 $A_j, B_j, T_j$ $(1 \leq A_j \leq N, 1 \leq B_j \leq N, A_j \ne B_j)$ が空白を区切りとして書かれている．これは，木 $A_j$ と木 $B_j$ の間を相互に $T_j$ 秒で飛び移ることができることを表している．また，$1 \leq j < k \leq M$ ならば，$(A_j, B_j) \ne (A_k, B_k)$ および$(A_j, B_j) \ne (B_k, A_k)$ を満たす．

出力

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

制限

すべての入力データは以下の条件を満たす．

• $2 \leq N \leq 100000$
• $1 \leq M \leq 300000$
• $1 \leq H_i \leq 1000000000 (1 \leq i \leq N)$
• $1 \leq T_j \leq 1000000000 (1 \leq j \leq M)$
• $0 \leq X \leq H_1$

入出力例

入力例 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

---