4 Sugar Glider

In the forest where JOI the sugar glider lives, there are $N$ eucalyptus trees, numbered from $1$ to $N$. The height of tree $i$ is $H_i$ meters.

There are $M$ pairs of trees between which JOI can jump directly, and the time required to jump between each pair is fixed. While JOI is jumping between trees, his height from the ground decreases by $1$ meter per second. That is, if JOI's current height from the ground is $h$ meters and the time required to jump between the trees is $t$ seconds, his height after the jump will be $h - t$ meters. However, he cannot make the jump if $h - t$ is less than $0$ or if $h - t$ is greater than the height of the destination tree.

Furthermore, JOI can move up and down the side of a tree, allowing him to increase or decrease his height from the ground within the range of $0$ meters to the current tree's height. It takes $1$ second for JOI to increase or decrease his height from the ground by $1$ meter.

JOI wants to go from a position at height $X$ meters on tree $1$ to the top of tree $N$ (a position at height $H_N$ meters), and he wants to know the minimum time required to do so.

Task

Given the height of each tree, information about the pairs of trees JOI can jump between, and the initial height of JOI, write a program to find the minimum time required to reach the top of tree $N$.

Input

Read the following data from standard input:

• The first line contains three space-separated integers $N, M, X$. This indicates that there are $N$ trees, $M$ pairs of trees between which he can move, and JOI is initially at a height of $X$ meters on tree $1$.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains an integer $H_i$, representing the height of tree $i$ in meters.
• The $j$-th line of the following $M$ lines ($1 \le j \le M$) contains three space-separated integers $A_j, B_j, T_j$ ($1 \le A_j \le N, 1 \le B_j \le N, A_j \neq B_j$), representing that it is possible to jump between tree $A_j$ and tree $B_j$ in $T_j$ seconds. Also, for $1 \le j < k \le M$, $(A_j, B_j) \neq (A_k, B_k)$ and $(A_j, B_j) \neq (B_k, A_k)$.

Output

Output the minimum time in seconds required to go from the position at height $X$ meters on tree $1$ to the top of tree $N$ as an integer on a single line. If there is no such way, output $-1$ instead.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [25 points]

The following conditions are satisfied:

• $N \le 1\,000$.
• $M \le 3\,000$.
• $H_i \le 100$ ($1 \le i \le N$).
• $T_j \le 100$ ($1 \le j \le M$).

Subtask 2 [25 points]

The following condition is satisfied:

• $X = 0$.

Subtask 3 [50 points]

There are no additional constraints.

Examples

Input 1

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

Output 1

110

Note 1

For example, he can move as follows: 1. Climb tree $1$ by $50$ meters. 2. Jump from tree $1$ to tree $2$. 3. Jump from tree $2$ to tree $4$. 4. Jump from tree $4$ to tree $5$. 5. Climb tree $5$ by $10$ meters.

Input 2

2 1 0
1
1
1 2 100

Output 2

-1

Note 2

JOI cannot jump from tree $1$ to tree $2$.

Input 3

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

Output 3

100