题目描述

飞天鼠 JOI 君住着的森林里长着编号为 $1$ 到 $N$ 的 $N$ 棵桉树。第 $i$ 棵树的高度是 $H_i$ 米。

JOI 君能在其中的 $M$ 对桉树之间直接飞行，在各对树木之间飞行所需的时间是固定的。当 JOI 君在树木之间飞行的时候，他离地面的高度会每秒下降 $1$ 米。也就是说，如果 JOI 君现在离地高度是 $h$ 米，在树木之间飞行需要 $t$ 秒，那么飞行之后的离地高度就会变成 $h-t$ 米。当 $h-t$ 小于 $0$ 或大于目标树木的高度时则不能飞行。

JOI 君还能沿着树的侧面上下移动，使得他的离地高度在 $0$ 到当前所在树木高度的范围内变化。JOI 君每使自己的离地高度增加或减少 $1$ 米都需要 $1$ 秒的时间。

JOI 君要从 $1$ 号树木上高度为 $X$ 米的位置出发，到树木 $N$ 的顶端（高度为 $H_N$ 米的位置）去。他想知道为了达成这个目标所需时间的最小值。

给出各棵树木的高度、JOI 君能直接飞行的树木对和 JOI 君最初所在位置的高度，请求出到达树木 $N$ 顶端所需时间的最小值。

输入格式

第一行包含三个以空格分开的整数 $N$, $M$ 和 $X$，意义分别与题目描述中的 $N$, $M$ 和 $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, B_j \le N, A_j \ne B_j)$，表示 JOI 君能花 $T_j$ 秒的时间从 $A_j$ 飞到 $B_j$ 或从 $B_j$ 飞到 $A_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$。

样例 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

下列是其中一种最优解：

• 沿着树木 $1$ 向上爬 $50$ 米。
• 从树木 $1$ 飞到树木 $2$。
• 从树木 $2$ 飞到树木 $4$。
• 从树木 $4$ 飞到树木 $5$。
• 沿着树木 $5$ 向上爬 $10$ 米。

样例 2

输入

2 1 0
1
1
1 2 100

输出

-1

JOI 君无法从树木 $1$ 飞到树木 $2$。

样例 3

输入

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

输出

100

数据范围与提示

全部的输入数据满足：

• $2 \le N \le 100000$
• $1 \le M \le 300000$
• $1 \le H_i \le 10^9$ $(1 \le i \le N)$
• $1 \le T_j \le 10^9$ $(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 分）
没有额外限制。