问题描述
有一个简单的小游戏。游戏的主人公是一个勇士，他要穿过一片黑森林，去解救公主。
黑森林的地图可以用一张$V$个点、$E$条边的无向图来描述，起点是$1$号点，终点是$V$号点，通过每条边的时间均为一。
图的边上有荆棘毒刺，而点上有供休憩的小木屋，勇士每一次经过一条边会损失一定的$HP$，每一次到达一个点则会加上一定的$HP[i]$。
当$HP \leq 0$时，勇士死亡；$HP$的上限为$M$，当某一次休憩后$HP \gt M$时，$HP$将只能保留$M$。
勇士要从起点出发，出发时$HP$为$M$，在保证存活的前提下，尽快地到达目的地。
输入格式
第一行三个整数，$V$、$E$、$M$。
第二行$V$个整数，表示每个点每经过一次增加的HP值。
接下来$E$行，每行三个整数$x$、$y$、$z$，表示$x$号点到$y$号点有一条边，每经过一次消耗$z$的$HP$。
输出格式
一行一个整数，表示到达终点的最少时间。若无法到达，则输出-1。
样例输入
5 5 3
3 2 3 2 3
1 5 4
1 2 1
2 3 2
3 4 1
4 5 2样例输出
4样例解释
走路径1——2——3——4——5。
数据规模
| 测试点编号 | V= | E= | M= | z∈ | HP[i]∈ |
|---|---|---|---|---|---|
| 1 | 5 | 10 | 10 | [0,20] | [0,3] |
| 2 | 5 | 10 | 10 | [0,20] | [0,3] |
| 3 | 5 | 10 | 10 | [0,20] | [0,3] |
| 4 | 20 | 50 | 20 | [0,40] | [0,10] |
| 5 | 100 | 500 | 20 | [0,40] | [0,10] |
| 6 | 500 | 1000 | 500 | [0,500] | [0,200] |
| 7 | 1000 | 5000 | 1000 | [0,3000] | [0,200] |
| 8 | 10000 | 50000 | 10000 | [0,10000] | [0,100] |
| 9 | 30000 | 100000 | 20000 | [0,20000] | [0,100] |
| 10 | 30000 | 100000 | 20000 | [0,20000] | [0,100] |
对于$100\%$的数据，保证图结构随机生成，保证$z$和$HP[i]$在对应范围内随机生成。
