Problem Description

In the forest where the wombat JOI 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 needed to jump between each such pair is fixed. While JOI is jumping between trees, his height above the ground decreases at a rate of $1$ meter per second. That is, if JOI’s current height above the ground is $h$ meters, and it takes $t$ seconds to jump between two trees, then his height above the ground after the jump will be $h - t$ meters. However, if $h - t$ is less than $0$ or greater than the height of the destination tree, then this jump cannot be performed.

In addition, JOI can move up and down along the side of a tree to adjust his height above the ground within the range from $0$ meters to the height of the tree he is currently on. It takes $1$ second for JOI to increase or decrease his height above the ground by $1$ meter.

JOI wants to go from a position on tree $1$ at height $X$ meters above the ground to the top of tree $N$ (that is, the position at height $H_N$ meters above the ground). He wants to know the minimum time needed to achieve this.

Task

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

Input Format

Read the following data from standard input.

• The first line contains three space-separated integers $N, M, X$. This means there are $N$ trees, $M$ pairs of trees that can be jumped between, and initially JOI is on tree $1$ at height $X$ meters above the ground.
• In the next $N$ lines, the $i$-th line ($1 \le i \le N$) contains one integer $H_i$, meaning that tree $i$ has height $H_i$ meters.
• In the next $M$ lines, the $j$-th line ($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 \ne B_j$). This means JOI can jump in both directions between tree $A_j$ and tree $B_j$, and the required time is $T_j$ seconds. Also, for $1 \le j < k \le M$, it holds that $(A_j, B_j) \ne (A_k, B_k)$ and $(A_j, B_j) \ne (B_k, A_k)$.

Output Format

Output one line to standard output containing one integer: the minimum time (in seconds) needed to reach the top of tree $N$ starting from the position on tree $1$ at height $X$ meters above the ground. If it is impossible to reach, output $-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

Sample Explanation 1

For example, you can move in the following way:

1. Climb up $50$ meters on tree 1.
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 up $10$ meters on tree 5.

Sample Explanation 2

JOI cannot jump from tree 1 to tree 2.

Constraints

All input data satisfy the following conditions.

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

Subtasks

Subtask 1 [25 points]

The following conditions are satisfied.

• $N \le 1000$
• $M \le 3000$
• $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.

Translated by DeepSeek V3.2.

Translated by ChatGPT 5