CF2110D Fewer Batteries

在 2077 年机器人统治世界后，它们决定进行以下比赛。 有 $n$ 个检查点，第 $i$ 个检查点包含 $b_i$ 块电池。机器人最初从第 $1$ 个检查点出发，不带任何电池，必须到达第 $n$ 个检查点。 检查点之间共有 $m$ 条单向通道。第 $i$ 条通道允许从点 $s_i$ 移动到点 $t_i$（$s_i < 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 < t_i \leq n$，$1 \leq w_i \leq 10^9$）——通道的起点、终点和通过所需的最低电池数量。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。 保证所有测试用例的 $m$ 之和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出旅程结束时能够拥有的最少电池数量，如果无法到达点 $n$，则输出 $-1$。

在第一个测试用例中，需要在起点获取 $1$ 块电池，然后移动到点 $2$，再移动到点 $3$。 在第二个测试用例中，需要在起点获取 $2$ 块电池，移动到点 $2$ 再获取 $2$ 块电池，移动到点 $4$，最后移动到点 $5$。 在第三个测试用例中，没有从点 $1$ 到点 $n$ 的路径。 在第四个测试用例中，需要在起点获取 $1$ 块电池，移动到点 $2$ 再获取 $9$ 块电池，移动到点 $3$，最后移动到点 $4$。 翻译由 DeepSeek V3 完成