AT_abc362_d [ABC362D] Shortest Path 3

[problemUrl]: https://atcoder.jp/contests/abc362/tasks/abc362_d $ N $ 頂点 $ M $ 辺の単純連結無向グラフが与えられます。頂点 $ i\,(1\leq\ i\ \leq\ N) $ は重み $ A_i $ を持ちます。また、辺 $ j\,(1\leq\ j\ \leq\ M) $ は頂点 $ U_j,V_j $ を双方向に結び、重み $ B_j $ を持ちます。 このグラフ上のパスの重みを、パス上に現れる頂点の重みと辺の重みの総和と定義します。 各 $ i=2,3,\dots,N $ について、以下の問題を解いてください。 - 頂点 $ 1 $ から頂点 $ i $ までのパスであって、重みが最小となるものの重みを求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ U_1 $ $ V_1 $ $ B_1 $ $ U_2 $ $ V_2 $ $ B_2 $ $ \vdots $ $ U_M $ $ V_M $ $ B_M $

$ i=2,3,\dots,N $ に対する答えを、この順に空白区切りで一行で出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ N-1\ \leq\ M\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ U_j\