グラフ上の最短距離を求めるアルゴリズムはいくつかありますが、今回はダイクストラ法を使います。
ダイクストラ法は、今回のように辺の重みが全て非負のグラフにおいて使用することができます。\(1\) つ始点となる頂点 \(s\) を決めて実行すると、全ての \(i (1 \le i \le N)\) について頂点 \(s\) から頂点 \(i\) への最短距離(到達不可能な場合はその旨)を求めることができ、計算量は \(O((N + M) \log(N))\) です。(実装によって \(O(N^2 + M)\) や \(O(M + N\log(N))\) のバージョンもあります)

この問題では、各 \(k\) について

1. 頂点 \(1\) から頂点 \(k\) への最短距離 (到達不可能な場合はその旨)
2. 頂点 \(k\) から頂点 \(N\) への最短距離 (到達不可能な場合はその旨)

が求まればよいです。
1. は \(s = 1\) としてダイクストラ法を実行すれば求まります。2. も、元のグラフの辺の向きを全て逆にしたグラフ上で \(s = N\) としてダイクストラ法を実行すれば求まります。
ダイクストラ法 \(2\) 回で答えが求まり、全体の計算量は \(O((N + M) \log(N))\) となります。