题目描述

最近，举世闻名的蓝宝石“绀青之拳”即将展出，作为闻名世界的宝石大盗，怪盗基德自然要来“光顾”一下。

现在一共有 $N$ 栋高楼，编号从 $1$ 到 $N$，每栋楼都有 $h_i$ 层。初始的时候，基德在 $1$ 号楼，蓝宝石在 $N$ 号楼。为了能够更好的潜入 $N$ 号楼，基德决定使用滑翔翼从空中潜入。

由于空中安保力量的部署，基德只能在其中 $M$ 对高楼中直接使用滑翔翼飞行。由于高楼之间的距离固定，在各对高楼间的飞行时间也是固定的。当使用滑翔翼飞行的时候，每秒钟基德的高度会下降1层楼。也就是说，当基德从第 $x$ 号楼的第 $h$ 层楼开始滑行时，从 $x$ 号楼 到 $y$ 号楼的飞行时间为 $t$，他降落到 $y$ 号楼时将会在 $h-t$ 层楼。当 $h-t < 0$ 或者 $h-t>h_y$ 时，他将不能使用滑翔翼飞行。

同时，他还能在同一栋楼中通过楼梯上下移动，也即每秒钟基德可以往上或者往下一层楼。当然，他能移动的高度只能在 $0$ 到当前楼栋的最大层数这个范围内。

由于绀青之拳展出在 $N$ 号楼的楼顶，现在基德要从 $1$ 号楼的 $X$ 层的位置出发，到 $N$ 号楼的顶楼（$h_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})$，表示基德能花 $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

输入 #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

2 1 0
1
1
1 2 100

输出 #2

-1

输入输出样例 #3

输入 #3

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

输出 #3

100

说明/提示

【样例解释】

对于样例1，下列是其中一种最优解：

1. 沿着 1 号楼向上爬 50 层。
2. 从 1 号楼滑翔到 2 号楼。
3. 从 2 号楼滑翔到 4 号楼。
4. 从 4 号楼滑翔到 5 号楼。
5. 沿着 5 号楼向上爬 10 层。

对于样例2，无法从 1 号楼到 2 号楼。

【数据范围】