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

制限

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

• $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 点]

追加の制限はない．

入力例 1Copy

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

出力例 1Copy

110

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

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

入力例 2Copy

2 1 0
1
1
1 2 100

出力例 2Copy

-1

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

入力例 3Copy

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

出力例 3Copy

100