(特別な前計算などはせずに) 各町 \(i\) ごとに答えを求めます。
町 \(i\) から出発する、かかる時間が最小の正しい散歩経路は以下のどちらかです。

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

前者のコストは自明なので後者の最小コストを考えます。
町 \(i\) を始点にダイクストラ法を使うと、町 \(i\) から各町 \(j\) への距離が求まります。また、すべての道路の向きを反転したグラフで同様に町 \(i\) からダイクストラ法を使うと、元のグラフで各町 \(j\) から町 \(i\) への最小コストが求まります。
これらを使えば答えを求めることができます。

以上を各 \(i\) について行うので計算量は \(O(N(N + M\log(M)))\) です。