町 \(i\) から出発するような、かかる時間が最小の正しい散歩経路は以下のどちらかです。

• 町 \(i\) から町 \(i\) 自身への道路を通るだけ
• 町\(i\) から町 \(j(j≠i)\) に最短距離で行き、また町 \(i\) に最短距離で帰ってくる

前者のコストは自明なので後者の最小コストを考えます。これは全頂点対についての最短距離が求まっていれば、\(j\) を全探索することで町ごとに \(O(N)\) で求めることができます。

各町を始点としたダイクストラ法を行うことで、全頂点対についての最短距離を \(O(N(N+M\log M))\) で求めることができるので、この問題は全体で \(O(N(N+M\log M) + N^2) = O(N(N+M\log M))\) で解けました。