AT_past202107_k 急ぎ旅

有一张 $n$ 点（编号 $1$ 到 $n$）$m$ 边（编号 $1$ 到 $m$）的无向图。边 $i$ 连接点 $u_i$ 和 $v_i$，长度为 $t_i$。每个点上写有一个整数，点 $i$ 上写的整数为 $a_i$。 请求出从点 $1$ 到点 $n$ 的路径中，找出路线**总长度尽可能短**并且**所经过的所有点上的数字之和最大**的路线，并输出所经过的所有点上的数字之和。（同一个点的数只算一次，包括点 $1$ 和点 $n$）

第一行为点数 $n(2 \le n \le 10^5)$ 和边数 $m(n-1 \le m \le 2 \times 10^5)$。 第二行为 $n$ 个整数 $a_i(1 \le a_i \le 10^9)$。 接下来 $m$ 行，每行三个整数 $u_i,v_i,t_i(1 \le u_i,v_i \le n，u_i \neq v_i，1 \le t_i \le 10^9)$。保证图联通。

一行一个整数。

### 注意 この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ つの都市の間もいくつかの道を経由して移動することができる ### Sample Explanation 1 $ 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 $ となります。 ### Sample Explanation 2 答えが $ 32 $ bit 整数に収まらない可能性がある事に注意してください。