Problem Description

JOI, the sugar glider, lives in a forest where 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 directly glide, and the time it takes to glide between each pair of trees is specified. While JOI is gliding between trees, his height above the ground decreases by $1$ meter per second. That is, if JOI's current height above the ground is $h$ meters and it takes $t$ seconds to glide between trees, his height after gliding will be $h - t$ meters. However, he cannot glide if $h - t$ is less than $0$ or greater than the height of the destination tree.

Additionally, JOI can move up or down the sides of a tree to change his height within the range from $0$ to the height of the tree he is on. It takes $1$ second for JOI to increase or decrease his height by $1$ meter.

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

Input Format

Read the following data from standard input:

• The first line contains the integers $N$, $M$, and $X$, separated by spaces. This indicates that there are $N$ trees, $M$ pairs of trees between which JOI can glide, and JOI starts at a height of $X$ meters on tree $1$.
• The next $N$ lines contain an integer $H_i$ each, indicating the height of tree $i$ in meters.
• The next $M$ lines contain three integers $A_j$, $B_j$, and $T_j$ (where $1 \leq A_j \leq N$, $1 \leq B_j \leq N$, and $A_j \neq B_j$), separated by spaces. This indicates that JOI can glide between tree $A_j$ and tree $B_j$ in $T_j$ seconds. Additionally, for $1 \leq j < k \leq M$, $(A_j, B_j) \neq (A_k, B_k)$ and $(A_j, B_j) \neq (B_k, A_k)$.

Output Format

Output to standard output a single integer representing the minimum time in seconds to go from a height of $X$ meters on tree $1$ to the top of tree $N$. If there is no way to reach the top, output $-1$ instead.

Sample Input and Output

Sample 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

Sample Output #1

110

Sample Input #2

2 1 0
1
1
1 2 100

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

100

Notes/Hints

Task

Given the height of each tree, the pairs of trees between which JOI can glide directly, and the initial height where JOI is located, create a program to find the minimum time required to reach the top of tree $N$.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [25 points]

Satisfies the following conditions:

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

Subtask 2 [25 points]

Satisfies the following conditions:

• $X = 0$.

Subtask 3 [50 points]

No additional constraints.

Sample Explanation 1

For example, the following movements are possible:
1. Climb tree $1$ to $50$ meters.
2. Glide from tree $1$ to tree $2$.
3. Glide from tree $2$ to tree $4$.
4. Glide from tree $4$ to tree $5$.
5. Climb tree $5$ to $10$ meters.

Sample Explanation 2

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

见题面 Input 部分

见题面 Output 部分