D - 単一始点最短経路問題 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N個の街があり、0, 1, 2, ..., N-1と番号がついています。また、M本の道があり、0, 1, 2, ..., M-1と番号がついています。

道iは街u_iから街v_iへの一方通行の道で、通るのにc_i分かかります。街0から1本以上の道を通って街N-1に到達できることがわかっています。

街0から街N-1まで移動するとき、必要な時間の最小値を出力してください。

制約

  • 入力は全て整数である
  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 0 \leq u_i, v_i \lt N (0 \leq i \lt M)
  • u_i \neq v_i (0 \leq i \lt M)
  • 0 \leq c_i \leq 10^9 (0 \leq i \lt M)
  • 街0から1本以上の道を通って街N-1に到達できる

入力

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

N M
u_0 v_0 c_0
u_1 v_1 c_1
:
u_{M-1} v_{M-1} c_{M-1}

出力

街0から街N-1まで移動するために必要な時間の最小値を出力せよ。

入力例 1

3 4
0 1 1
1 0 2
1 2 3
2 0 4

出力例 1

4

与えられる入力は下図のようになっています。

例

街0から街1へ道0を使って1分で移動し、街1から街2へ道2を使って3分で移動することで、合計4分で移動できます。