課題

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

入力

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

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

出力

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

制限

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

• $2 \leqq N \leqq 100\,000$．
• $1 \leqq M \leqq 300\,000$．
• $1 \leqq H_i \leqq 1\,000\,000\,000$ ($1 \leqq i \leqq N$)．
• $1 \leqq T_j \leqq 1\,000\,000\,000$ ($1 \leqq j \leqq M$)．
• $0 \leqq X \leqq H_1$．

小課題

小課題 1 [25 点]

以下の条件を満たす．

• $N \leqq 1\,000$．
• $M \leqq 3\,000$．
• $H_i \leqq 100$ ($1 \leqq i \leqq N$)．
• $T_j \leqq 100$ ($1 \leqq j \leqq 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