2077年,当机器人统治世界时,他们决定参加以下游戏。
有 $$$n$$$ 个检查点,第 $$$i$$$ 个检查点包含 $$$b_i$$$ 电池。最初,机器人在没有电池的情况下从第 $$$1$$$ 个检查点开始,并且必须到达第 $$$n$$$ 个检查点。
检查站之间总共有$$$m$$$单向通道。第 $$$i$$$ 通道允许从点 $$$s_i$$$ 移动到点 $$$t_i$$$ ($$$s_i \lt t_i$$$),但反之则不然。此外,只有当机器人至少有 $$$w_i$$$ 充电电池时才能使用第 $$$i$$$ 通道;否则,途中就会没电了。
当机器人到达 $$$v$$$ 点时,它还可以额外携带从 $$$0$$$ 到 $$$b_v$$$(含)之间的任意数量的电池。此外,它始终携带所有先前收集的电池,并且在每个检查点,它都会对所有先前收集的电池进行充电。
求机器人在旅程结束时可以拥有的最小电池数量,或者报告不可能从第一个检查点到达最后一个检查点。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 0 \leq m \leq 3 \cdot 10^5$$$)——分别是检查点的数量和通道的数量。
第二行包含 $$$n$$$ 数字 $$$b_i$$$ ($$$0 \leq b_i \leq 10^9$$$) — 第 $$$i$$$ 个检查点的电池数量。
接下来的 $$$m$$$ 行包含三个整数 $$$s_i, t_i, w_i$$$ ($$$1 \leq s_i \lt t_i \leq n, 1 \leq w_i \leq 10^9$$$) — 通道的端点以及通过通道所需的最小电池数量。
保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$。
保证$$$m$$$之和不超过$$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出旅程结束时可以拥有的最小电池数量,如果无法到达点 $$$n$$$,则输出 $$$-1$$$。
示例
输入复制
43 32 0 01 2 12 3 11 3 25 62 2 5 0 11 2 21 3 11 4 33 5 52 4 44 5 32 01 14 43 10 0 01 2 11 3 32 3 103 4 5
输出复制
1 4 -1 10
注意
在第一个测试用例中,您需要在起点处获取$$$1$$$电池,然后移动到点$$$2$$$,然后移动到点$$$3$$$。
在第二个测试用例中,您需要在起始点拿$$$2$$$电池,然后移动到点$$$2$$$,再拿$$$2$$$电池,移动到点$$$4$$$,然后移动到点$$$5$$$。
在第三个测试用例中,没有从点 $$$1$$$ 到点 $$$n$$$ 的路径。
在第四个测试用例中,您需要在起点处拿$$$1$$$电池,然后移动到点$$$2$$$,再拿$$$9$$$电池,移动到点$$$3$$$,然后移动到点$$$4$$$。