解题思路与方法

题意回顾与抽象

• 有 $n$ 个营地（1 到 $n$），从 1 出发到 $n$ 结束。
• 到达营地 $i$ 时可把携带的“补给包数量”增加不超过 $A_i$ 个（不能减少），并且“之前带上的包都会被补满”（这只影响“内容”，不影响“数量”）。
• 单向边 $(u\to v)$ 需要当前携带数量 $\ge W_{uv}$ 才能走。
• 初始在 1，携带 0 个。目标：能到 $n$，且到达时携带数量最小。

等价地把携带的包当作一个非减的数值序列；在每个营地最多再拿 $A_i$ 个；每条边要求当前数值 $\ge W$。

题目内容

多多最近迷上了登山挑战，准备完成一次从山脚(第 $1$ 座营地)出发、最终抵达山顶(第 $n$ 座营地)的攀登路线。

多多本次要挑战的山峰一共有 $n$ 座营地，编号为 $1$ 到 $n$ 。第 $i$ 座营地提供 $Ai$ 个“补给包”，离开营地 $i$ 时，多多可以选择额外带走不超过 $Ai$ 个、任意数量 的补给包，但不能放下已经携带的补给包。多多每次抵达一个营地时，所有之前带上的补给包都会被重新补满。

一共有 $m$ 条单向路线连接着这些营地，第 $i$ 条路线连接从营地 $Ui$ 到 $Vi$ 的路(保证 $Ui<Vi$ )，多多想要通过第 $i$ 条路线，必须随身携带至少 $Wi$ 个补给包，否则中途会因资源不足而放弃。

初始时，多多在第 $1$ 座营地，手中没有任何补给包。目标是抵达第 $n$ 座营地，完成本次登山挑战。请你帮多多规划路线，使得在成功抵达终点时，多多携带的补给包数量最少。

输入描述

第一行包括两个整数，营地数 $n$ 和路线数 $m(2≤n≤1×10^5,0≤m≤5×10^5)$。

第二行包括 $n$ 个整数 $A_1,A_2,...,A_n(0 ≤ Ai≤ 10^9)$ ，表示每个营地可获取的补给包数量。

接下来 $m$ 行，每行包含三个整数 $Ui,Vi,Wi (1≤ Ui<Vi≤n,1≤Wi≤10^9)$ ,表示从营地 $Ui$ 到 $Vi$ 的单向路线最少需要携带 $Wi$ 个补给包。

输出描述

输出成功抵达终点时多多携带的最少补给包数量。

若无法抵达第 $n$ 座营地，请输出 $-1$ 。

样例1

输入

5 6
2 5 2 0 1
1 2 1
2 5 5
1 3 2
3 4 4
1 4 3
4 5 3

输出

4

说明

在营地 $1$ 带走 $2$ 个补给包，移动到营地 $3$ ；在营地 $3$ 带走 $2$ 个补给包，移动到营地 $4$ ；在营地 $4$ 补充完毕，移动到营地 $5$ ，抵达终点。

*营地 $1$ 只有 $2$ 个补给包，无法直接移动到营地 $4$ 。