K - Flying Trip Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

AtCoder 王国には都市 1 , 都市 2 , \ldots , 都市 N の N 個の都市と、 これらの都市を双方向に結ぶ道 1 , 道 2 , \ldots , 道 M の M 本の道があり、 どの 2 つの都市の間もいくつかの道を経由して移動することができます。 具体的には道 i は都市 U_i と 都市 V_i を結び、 一方の都市からもう一方の都市まで T_i 時間で移動できます。
さらに、都市にはそれぞれ景観と呼ばれる数値が定まっており、都市 i の景観は A_i です。 ある都市から別の都市へ 1 つ以上の道を経由して移動したとき、 その移動にかかる時間は使用したそれぞれの道の所要時間の総和であり、 その移動の満足度は始点と終点を含め、その移動の過程で通った都市の景観の総和で表されます。 ただし、満足度について、同じ都市を 2 回以上経由してもその都市の景観は 1 回しかカウントしません。

高橋君は今都市 1 におり、都市 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
  • 入力は全て整数
  • どの 2 つの都市の間もいくつかの道を経由して移動することができる

入力

入力は以下の形式で標準入力から与えられる。

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 です。
他に移動時間が 5 となるような移動の方法は存在しません。 例えば、1\to 2\to 3\to 4 と移動すると満足度は 17 ですが、移動時間が 6 となるため、最短ではありません。 また、移動時間が 4 以下となるような都市 1 から都市 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 bit 整数に収まらない可能性がある事に注意してください。

Score : 6 points

Warning

Do not make any mention of this problem until July 17, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

There are N cities in the Kingdom of AtCoder called City 1, City 2, \ldots, City N, and M roads called Road 1, Road 2, \ldots, Road M that connect the cities bidirectionally, so that you can travel between any two cities using some number of roads. Specifically, Road i connects City U_i and City V_i, and it enables you to get from either city to the other city in T_i hours.
Additionally, each city has a fixed value called scenery; the scenery of City i is A_i. When you travel from a city to another city by using one or more roads, the time needed for that travel will be the sum of the times it takes to get through the individual roads, and the satisfaction of that travel will be the sum of the sceneries of the cities visited during the travel, including the starting point and the destination. Here, the scenery of a city contributes to the satisfaction only once, even if that city is visited more than once.

Takahashi is now in City 1 and wants to get to City N. Since he is in a hurry, he wants to minimize the time it takes to travel, and maximize the satisfaction of the travel on the condition that the time needed is minimized. Find the satisfaction of the travel that meets these criteria.

Constraints

  • 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
  • All values in input are integers.
  • It is possible to travel between any two cities using some number of roads.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

4 5
2 5 7 3
1 2 1
1 3 2
2 4 4
3 4 3
2 3 2

Sample Output 1

12

If we follow the path 1\to 2\to 4, the time needed will be 5, which is the minimum possible, and the satisfaction will be 10.
If we follow the path 1\to 3\to 4, the time needed will be 5, which is the minimum possible, and the satisfaction will be 12.
There is no other path that minimizes the time needed.
For example, the path 1\to 2\to 3\to 4 will have the satisfaction of 17, but the time needed will be 6, which is not the minimum possible. Additionally, there is no path from City 1 to City 4 such that the time needed is 4 or less.
Thus, the answer is 12.

Sample Input 2

6 5
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

Sample Output 2

6000000000

Note that the answer may not fit into a 32-bit integer.