The Closest Hospital

There are n cities, connected by m bidirectional roads. Each city can be either a regular city or a city with a hospital. Your task is to find, for each city, the closest hospital based on the road network.


The first line contains two space-separated integers, n and m (), representing the number of cities and the number of roads, respectively.
The second line contains n space-separated integers (0 or 1), where represents the hospital status of city i. If is 1, city i has a hospital.
The next m lines each contain three space-separated integers , and (, ), representing a bidirectional road between cities and with length .
It is guaranteed that the cities are connected and there is at least one hospital.


Output a single line containing n space-separated integers, where the i-th integer represents the distance from the closest hospital to city i.


5 4 0 1 0 1 0 1 2 5 1 3 2 4 5 10 4 3 6
5 0 6 0 10


Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue