在梦中,露西发现自己身处迷宫之中。该迷宫由 $$$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