Given N towns in a country of which P have hospitals and M bidirectional roads connecting them. Find the minimum distance of each town that does not have a hospital to the nearest hospital.
N, M <= 10^5 and P <= N.
Using Floyd Warshall or Dijkstra will push it to N^3 or N^2 log N. How to do it within the limits?