飞天鼠

译自 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 \lt k \le M$ ，满足 $(A_{j},B_{j}) \neq(A_{k},B_{k})$ 且 $(A_{j},B_{j}) \neq(B_{k},A_{k})$ 。

详情