分数: 6 点
警告
2021 年 7 月 17 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
有 N AtCoder王国的城市称为City 1, 城市 2, \ldots, 城市 N,和 M 道路称为路 1, 路 2, \ldots, 路 M 双向连接城市,以便您可以使用一定数量的道路在任意两个城市之间旅行。
具体来说,路 i 连接城市 U_i 和城市 V_i,它使您能够从任意一个城市到达另一个城市 T_i 小时。
此外,每个城市都有一个固定值,称为 风景;城市风光 i is A_i。
当您使用一条或多条道路从一个城市前往另一个城市时,该旅行所需的时间将是通过各条道路所需时间的总和,以及 满意
该行程的 将是行程中所到过的城市的风景总和,包括出发地和目的地。
在这里,一个城市的风景只会带来一次满足感,即使这个城市被参观了不止一次。
高桥现在在城市 1 想要前往 City N。由于他很赶时间,所以他想尽量减少旅行的时间,在尽量减少所需时间的条件下,最大限度地提高旅行的满意度。找到满足这些标准的旅行满意度。
约束
- 2 \leq N \leq 10^5
- N-1 \leq M \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq U_i,V_i \leq N
- U_i \neq V_i
- 1 \leq T_i \leq 10^9
- 输入中的所有值都是整数。
- 可以使用一定数量的道路在任意两个城市之间行驶。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \ldots A_N U_1 V_1 T_1 U_2 V_2 T_2 : U_M V_M T_M
输出
打印答案。
示例输入 1
4 5 2 5 7 3 1 2 1 1 3 2 2 4 4 3 4 3 2 3 2
示例输出 1
12
如果我们沿着这条路走 1\to 2\to 4,所需时间为 5,这是可能的最小值,满意度将为 10.
如果我们沿着这条路走 1\to 3\to 4,所需时间为 5,这是可能的最小值,满意度将为 12.
没有其他途径可以最大限度地缩短所需时间。
例如,路径 1\to 2\to 3\to 4 将会满意 17,但所需的时间是 6,这不是可能的最小值。此外,没有从 City 出发的路径 1 前往城市 4 这样所需的时间是 4 或更少。
因此,答案是 12.
示例输入 2
6 5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000
示例输出 2
6000000000
请注意,答案可能不适合 32位整数。