AT_past202107_k 急ぎ旅

[problemUrl]: https://atcoder.jp/contests/past202107-open/tasks/past202107_k 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 $ まで移動したいと考えています。高橋君は急いでいるので、移動にかかる時間を最短にした上で、その移動の満足度をなるべく大きくしたいと考えています。このとき高橋君の移動の満足度を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

答えを出力せよ。

### 注意 この問題に対する言及は、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 整数に収まらない可能性がある事に注意してください。