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

有 $M$ 对树之间，JOI 君可以直接相互跳跃，且每对树之间跳跃所需的时间是固定的。当 JOI 君在树与树之间跳跃时，其离地高度每秒会下降 1 米。也就是说，如果 JOI 君当前离地高度为 $h$ 米，跳跃所需时间为 $t$ 秒，则跳跃后的离地高度为 $h - t$ 米。但是，如果 $h - t < 0$ 或者 $h - t$ 大于目标树的高度，则无法进行该跳跃。

此外，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 \neq B_j$)，以空格分隔。这表示可以在树 $A_j$ 和树 $B_j$ 之间以 $T_j$ 秒的时间相互跳跃。此外，对于 $1 \le j < k \le M$，满足 $(A_j, B_j) \neq (A_k, B_k)$ 且 $(A_j, B_j) \neq (B_k, A_k)$。

输出格式

在标准输出中，输出一行，包含从树 1 高度 $X$ 米的位置前往树 $N$ 顶端所需的最短时间（以秒为单位）。如果无法到达，则输出 -1。

数据范围

所有输入数据满足以下条件：

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

子任务

子任务 1 [25 分]

满足以下条件：

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

子任务 2 [25 分]

满足以下条件：

• $X = 0$

子任务 3 [50 分]

无额外限制。

样例

输入格式 1

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

输出格式 1

110

说明

例如，可以按以下方式移动：

1. 在树 1 上爬升 50 米。
2. 从树 1 跳到树 2。
3. 从树 2 跳到树 4。
4. 从树 4 跳到树 5。
5. 在树 5 上爬升 10 米。

输入格式 2

2 1 0
1
1
1 2 100

输出格式 2

-1

说明

JOI 君无法从树 1 跳到树 2。

输入格式 3

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

输出格式 3

100