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

现在一共有 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< i< N) 行有一个整数 H{i}，表示楼栋 i 的层数有 H{i} 层。

接下来 M 行中，第  j(1< j< M)  行有三个以空格分开的整数  A{j},B{j},T{j} (1< A{j}, B{j}< N, A{j}\ne B{j})，表示基德能花  T{j} 秒的时间从  A{j}  滑翔到  B{j} 或从  B{j} 滑翔到  A{j}。 对于任意  1< j < k< M，满足  (A{j},B{j})!= (A{k},B{k}) 且 (A{j},B{j})!= (B{k},A{k})。