街 1 から街 \(i\) までの最短距離 \(S_i\) と街 \(N\) から街 \(i\) までの最短距離 \(T_i\) をそれぞれ Dijkstra 法で計算する.

このとき, 街 1 から街 \(k\) を経由して街 \(N\) までの最短距離は \(S_k + T_k\) となる.