题目描述：

有 $n$ 棵树，第 $i$ 棵树高 $h_i$ 米，一只小鼠初始位于 $1$ 号树 $X$ 高度。现有 $m$ 条航线，表示从 $u_i$ 号树飞到 $v_i$ 号树需要 $t_i$ 秒（是双向边！），飞行过程中它离地面的高度会每秒下降 $1$ 米，小鼠必须保证飞到 $v_i$ 号树时不会高于树，也不会低于地面，它可以通过在 $u_i$ 号树上以一米每秒的速度向上（向下）奔波完成！现在它需要到 $n$ 号树的最高处，请你求出最短时间，不能到达输出 $-1$ 。 $n,m\le 10^5~;~h_i,X,t_i\le 10^9$

输入格式：

第一行包含三个以空格分开的整数 $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})$，表示小鼠能花 $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

样例说明 1

下列是其中一种最优解：

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

样例解释 2

小鼠无法从树木 $1$ 飞到树木 $2$。

输入样例 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 分）

没有额外限制。