← 返回题目列表

AtCoder · past202107_k

K. 飞行之旅

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

分数: 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位整数。