问题描述

有一个简单的小游戏。游戏的主人公是一个勇士，他要穿过一片黑森林，去解救公主。

黑森林的地图可以用一张$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。

数据规模

对于$100\%$的数据，保证图结构随机生成，保证$z$和$HP[i]$在对应范围内随机生成。