CF1578L.Labyrinth

In a dream, Lucy found herself in a labyrinth. This labyrinth consists of $n$ rooms, connected by $m$ passages ($i$-th passage is $w_i$ cm wide). Each passage can be traversed in both directions. It is guaranteed that it is possible to get from any room to any other room. But this is not an ordinary labyrinth — each room in this labyrinth contains a magic candy. When Lucy eats this magic candy, she is getting wider. Specifically, if she eats candy from room $i$ she becomes wider by $c_i$ cm. Note that she is not obliged to eat candy the first time she visits a particular room, but she can eat each candy only once.

Unfortunately, passages in this labyrinth are pretty narrow, so after eating some candy, Lucy can get too wide and will not be able to traverse them — her width should not be greater than the width of the corresponding passage.

Lucy starts her journey in a room number $1$. She wants to eat all the candies. After that, she will just wake up, so she does not have to be able to return to the room $1$. She realizes that with her current width, she may not be able to do so, so she plans a workout before embarking on her journey. Lucy wants to know if it is possible to start with some positive width and still eat all the candies. If yes, then what is the maximal starting width with which it is possible.

在梦中，露西发现自己置身于一座迷宫之中。这座迷宫由 $n$ 个房间组成，房间之间通过 $m$ 条通道相连（第 $i$ 条通道宽 $w_i$ 厘米）。每条通道均可双向通行。保证任意两个房间之间均可达。但这并非一座普通迷宫——每个房间中都有一颗魔法糖果。当露西吃下某颗魔法糖果时，她的身体会变宽。具体而言，若她吃下第 $i$ 个房间中的糖果，则她的宽度将增加 $c_i$ 厘米。注意：她首次访问某个房间时并不一定要立即吃掉其中的糖果，但每颗糖果只能被吃一次。

不幸的是，这座迷宫中的通道十分狭窄；因此，在吃下若干糖果后，露西可能变得过宽，从而无法再通过某些通道——她的当前宽度不得超过所通行通道的宽度。

露西从编号为 $1$ 的房间出发。她希望吃掉所有糖果。之后她便会醒来，因此无需返回房间 $1$。她意识到，以自己当前的初始宽度，可能无法完成这一目标，因此她计划在启程前进行一番训练。露西想知道：是否存在某个正数初始宽度，使得她能够吃掉所有糖果？如果存在，那么满足条件的最大初始宽度是多少？

The first line contains two integers, $n$ and $m$ ($2 \le n \le 10^5; n - 1 \le m \le 10^5$) — the number of rooms and the number of passages.

The second line contains $n$ integers — $c_i$ ($1 \le c_i \le 10^9$).

Next $m$ lines contain three integers each — $a_i$, $b_i$ and $w_i$ ($1 \le a_i, b_i \le n; a_i \ne b_i; 1 \le w_i \le 10^9$) describing passage that connects rooms $a_i$ and $b_i$ and is $w_i$ cm wide. It is guaranteed that the resulting labyrinth is connected and there is at most one passage between any pair of rooms.

第一行包含两个整数 $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$ 厘米的通道。保证所构成的迷宫是连通的，且任意两个房间之间至多只有一条通道。

If it is possible to eat all the candies, output the maximal possible starting width, otherwise output $-1$.

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