Description

フクロモモンガの 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$ の頂上に行くためにかかる時間の最小値を求めるプログラムを作成せよ。

Input Format

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

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

Output Format

標準出力に，木 1 の高さ $X$ メートルの位置から木 $N$ の頂上に行くためにかかる時間の最小値を秒単位で表す整数を 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

110

2 1 0
1
1
1 2 100

-1

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

100

Hint

入出力例 1

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

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

入出力例 2

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

制限

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

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

小課題

小課題 1 [25 点]

以下の条件を満たす。

• $N \le 1000$
• $M \le 3000$
• $H_i \le 100$ ($1 \le i \le N$)
• $T_j \le 100$ ($1 \le j \le M$)

小課題 2 [25 点]

以下の条件を満たす。

• $X = 0$

小課題 3 [50 点]

追加の制限はない。