AT_joi2014ho4 フクロモモンガ (Sugar Glider)

有 $ 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$ 行中，第 $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 $ 行目には，整数 $ N,\ M,\ X $ が空白を区切りとして書かれている．これは，木の本数が $ N $ 本，移動できる木の組が $ M $ 組あり，最初 JOI 君が木 $ 1 $ の高さ $ X $ メートルの位置にいることを表す． - 続く $ N $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ N $) には，整数 $ H_i $ が書かれている．これは，木 $ i $ の高さが $ H_i $ メートルであることを表す． - 続く $ M $ 行のうちの $ j $ 行目 ($ 1\ \leqq\ j\ \leqq\ M $) には，整数 $ A_j,\ B_j,\ T_j $ ($ 1\ \leqq\ A_j\ \leqq\ N $，$ 1\ \leqq\ B_j\ \leqq\ N $，$ A_j\ \neq\ B_j $) が空白を区切りとして書かれている．これは，木 $ A_j $ と木 $ B_j $ の間を相互に $ T_j $ 秒で飛び移ることができることを表している．また，$ 1\ \leqq\ j\

输出到标准输出，仅一行一个整数，表示从树木 $1$ 上高度为 $X$ 米处移动到树木 $N$ 顶端所需时间的最小值（单位：秒）。如果不能到达目的地则输出 $-1$。 ## 样例： ### 输入样例 1 ```plain 5 5 0 50 100 25 30 10 1 2 10 2 5 50 2 4 20 4 3 1 5 4 20 ``` ### 输出样例 1 ```plain 110 ```

下列是其中一种最优解： 1. 沿着树木 $1$ 向上爬 $50$ 米。 1. 从树木 $1$ 飞到树木 $2$。 1. 从树木 $2$ 飞到树木 $4$。 1. 从树木 $4$ 飞到树木 $5$。 1. 沿着树木 $5$ 向上爬 $10$ 米。 ### 输入样例 2 ```plain 2 1 0 1 1 1 2 100 ``` ### 输出样例 2 ```plain -1 ``` ### 样例解释 2 小鼠无法从树木 $1$ 飞到树木 $2$。 ### 输入样例 3 ```plain 4 3 30 50 10 20 50 1 2 10 2 3 10 3 4 10 ``` ### 输出样例 3 ```plain 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 分） 没有额外限制。