CF1578L Labyrinth

在梦中，Lucy 发现自己身处一个迷宫。这个迷宫由 $n$ 个房间组成，房间之间通过 $m$ 条通道相连（第 $i$ 条通道宽度为 $w_i$ 厘米）。每条通道都可以双向通行。保证任意两个房间之间都可以互相到达。但这不是一个普通的迷宫——每个房间里都有一颗魔法糖果。当 Lucy 吃下某个房间的魔法糖果后，她的身体会变宽，具体来说，如果她吃下第 $i$ 个房间的糖果，她的宽度会增加 $c_i$ 厘米。注意，她第一次进入某个房间时不一定要吃糖果，但每颗糖果只能吃一次。 不幸的是，迷宫中的通道都很狭窄，所以在吃下某些糖果后，Lucy 可能会变得太宽而无法通过某些通道——她的宽度不能大于相应通道的宽度。 Lucy 从编号为 $1$ 的房间开始她的旅程。她想吃掉所有的糖果。之后她就会醒来，所以不需要回到 $1$ 号房间。她意识到以当前的宽度，可能无法做到这一点，因此她打算在出发前进行锻炼。Lucy 想知道，是否存在某个正的初始宽度，使得她能够吃掉所有的糖果。如果可以，最大可能的初始宽度是多少。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^5$，$n-1 \le m \le 10^5$），表示房间数和通道数。 第二行包含 $n$ 个整数 $c_i$（$1 \le c_i \le 10^9$）。 接下来的 $m$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $w_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$，$1 \le w_i \le 10^9$），表示一条连接房间 $a_i$ 和 $b_i$ 的宽度为 $w_i$ 厘米的通道。保证迷宫是连通的，且任意一对房间之间最多只有一条通道。

如果可以吃掉所有糖果，输出最大可能的初始宽度；否则输出 $-1$。

由 ChatGPT 4.1 翻译