AT_past202203_k 旅行計画

[problemUrl]: https://atcoder.jp/contests/past202203-open/tasks/past202203_k $ N $ 頂点 $ M $ 辺の重み付き有向グラフが与えられます。 頂点には $ 1 $ から $ N $ までの番号が振られています。 また、$ i\ (1\ \leq\ i\ \leq\ M) $ 本目の辺は頂点 $ u_i $ から頂点 $ v_i $ に向けて張られており、その重みは $ w_i $ です。 $ k=1,2,\ldots,N $ について、以下の問題を解いてください。 - 頂点 $ 1 $ から始めて頂点 $ k $ を一度以上通り、頂点 $ N $ まで行く経路が存在するか判定し、存在するならそのうち最短のものの長さを出力せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $ \hspace{0.8cm}\vdots $ $ u_M $ $ v_M $ $ w_M $

$ N $ 行にわたって出力せよ。$ i\ (1\ \leq\ i\ \leq\ N) $ 行目には $ k=i $ の場合の答えを以下に従って出力すること。 - 頂点 $ 1 $ から始めて頂点 $ k $ を一度以上通り、頂点 $ N $ まで行く経路が存在するなら、そのうち最短のものの長さを出力。 - 頂点 $ 1 $ から始めて頂点 $ k $ を一度以上通り、頂点 $ N $ まで行く経路が存在しないなら `-1` を出力。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ u_i,v_i\ \leq\ N $ - $ u_i\ \neq\ v_i $ - $ 1\ \leq\ w_i\ \leq\ 10^9 $ - 入力はすべて整数 ### Sample Explanation 1 \- $ k=1 $ のとき、$ 3 $ 本目の辺を通って直接頂点 $ 3 $ に移動する経路が最短です。 - $ k=2 $ のとき、$ 1 $ 本目の辺を通って頂点 $ 2 $ に移動したあと $ 2 $ 本目の辺を通って頂点 $ 3 $ に移動する経路が最短です。 - $ k=3 $ のとき、$ 3 $ 本目の辺を通って直接頂点 $ 3 $ に移動する経路が最短です。