P15814 [JOI 2014 Final] 蜜袋鼯 / Sugar Glider

袋熊 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$。

### 样例解释 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 完成