We will find the answer for each \(i\) (without any precomputation).
The valid walk that starts from town \(i\) with the minimum required time is either:

• such walk that uses only one road from town \(i\) to town \(i\) itself, or
• such walk that uses the shortest path from town \(i\) to town \(j (j \neq i)\), and then returns to town \(i\) using the shortest path

The cost of the former is obvious, so let us consider the latter.
If we apply Dijkstra’s algorithm from town \(i\), we can obtain the distance from town \(i\) to each town \(j\). Also, if we reverse all the directions of roads and similarly apply Dijkstra’s algorithm from town \(i\), we can find the minimum cost from each town \(j\) to town \(i\) in the original graph.
By using this, we can obtain the answer.

We perform this for each \(i\), so the time complexity is \(O(N(N + M\log(M)))\).