回家之路

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有 $n$ 座城市和 $m$ 个单向航班。乘坐航班 $(a,b,s)$ 前必须在城市 $a$ 且持有至少 $s$ 卢布，登机时会支付这笔钱。

你从城市 $1$ 出发，初始有 $p$ 卢布。在城市 $i$ 可以进行任意次表演，每次获得 $w_i$ 卢布。求到达城市 $n$ 所需的最少表演次数；如果无法到达，输出 $-1$。

输入格式

第一行包含测试组数 $t$。每组第一行包含 $n,m,p$；第二行包含 $w_1,\ldots,w_n$；随后 $m$ 行每行包含 $a,b,s$，表示一条从 $a$ 到 $b$、价格为 $s$ 的航班。

输出格式

对每组输出一个整数。

样例输入 1

4
4 4 2
7 4 3 1
1 2 21
3 2 6
1 3 8
2 4 11
4 4 10
1 2 10 1
1 2 20
2 4 30
1 3 25
3 4 89
4 4 7
5 1 6 2
1 2 5
2 3 10
3 4 50
3 4 70
4 1 2
1 1 1 1
1 3 2

样例输出 1

4
24
10
-1

数据范围

• $1\le t\le80$；
• $2\le n\le800$，$1\le m\le3000$；
• $0\le p\le10^9$，$1\le w_i,s_i\le10^9$；
• 所有测试组的 $n$ 之和不超过 $800$，$m$ 之和不超过 $3000$。