← 返回题目列表

Codeforces · 1578/L

L. 迷宫

中文机器翻译题面 查看原题

在梦中,露西发现自己身处迷宫之中。该迷宫由 $$$n$$$ 个房间组成,由 $$$m$$$ 通道连接(第 $$$i$$$ 通道宽 $$$w_i$$$ 厘米)。每条通道都可以从两个方向穿过。保证可以从任何房间到达任何其他房间。但这不是一个普通的迷宫——迷宫中的每个房间都含有一颗魔法糖果。当露西吃了这颗神奇的糖果后,她的肚子就变宽了。具体来说,如果她吃了 $$$i$$$ 房间里的糖果,她就会变宽 $$$c_i$$$ 厘米。请注意,她不必在第一次访问特定房间时吃糖果,但每种糖果只能吃一次。

不幸的是,这个迷宫中的通道非常狭窄,所以在吃掉一些糖果后,露西可能会变得太宽而无法穿过它们——她的宽度不应该大于相应通道的宽度。

露西在房间号 $$$1$$$ 开始她的旅程。她想吃掉所有的糖果。之后,她就会醒来,所以她不必能够返回房间$$$1$$$。她意识到以她目前的宽度,她可能无法做到这一点,因此她在踏上旅程之前计划了一次锻炼。露西想知道是否有可能以一定的正宽度开始并仍然吃掉所有糖果。如果是,那么可能的最大起始宽度是多少。

输入

第一行包含两个整数,$$$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$$$ 和 $$$a_i$$$ 的通道$$$b_i$$$ 宽 $$$w_i$$$ 厘米。保证最终的迷宫是相连的,并且任意一对房间之间最多有一条通道。

输出

如果有可能吃掉所有糖果,则输出最大可能的起始宽度,否则输出$$$-1$$$。

示例

输入 #1

3 3
1 2 3
1 2 4
1 3 4
2 3 6

输出 #1

3

输入 #2

2 1
1 1
1 2 1

输出 #2

-1