题目描述

译自 JOI 2014 Final T4「フクロモモンガ」

飞天鼠 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})$，表示 IOI 君能花 $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

输出 #1

110

输入 #2

2 1 0
1
1
1 2 100

输出 #2

-1

输入 #3

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

输出 #3

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 分）

没有额外限制。