说明

袋熊 JOI 君居住的森林里有 $N$ 棵桉树，这些树被编号为 $1$ 到 $N$。树 $i$ 的高度是 $H_i$ 米。

有 $M$ 对树，JOI 君可以直接在它们之间跳跃，并且在每对树之间跳跃所需的时间是固定的。JOI 君在树间跳跃时，离地高度会以每秒 $1$ 米的速度下降。也就是说，如果 JOI 君当前的离地高度是 $h$ 米，在两棵树之间跳跃需要 $t$ 秒，那么跳跃后的离地高度将是 $h - t$ 米。但是，如果 $h - t$ 小于 $0$ 或者大于目标树的高度，则无法进行这次跳跃。

此外，JOI 君可以通过在树的侧面上下移动，在 $0$ 米到当前所在树的高度范围内调整自己的离地高度。JOI 君将离地高度增加或减少 $1$ 米需要 $1$ 秒时间。

JOI 君想要从树 $1$ 上离地 $X$ 米高的位置，前往树 $N$ 的顶端（离地 $H_N$ 米高的位置），他想要知道完成这个目标所需的最短时间。

任务

给定每棵树的高度、JOI 君可以直接跳跃的树对信息以及 JOI 君的初始位置高度。编写程序，求出到达树 $N$ 顶端所需的最短时间。

输入格式

从标准输入读取以下数据。

• 第 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)$。

输出格式

向标准输出输出一行，包含一个整数，表示从树 $1$ 上离地 $X$ 米高的位置到达树 $N$ 顶端所需的最短时间（单位：秒）。如果无法到达，则输出 $-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

提示

样例解释 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 分]

没有额外限制。

翻译由 DeepSeek V3.2 完成