Algorithms and Data Structures

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.

Input

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

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

Examples

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

Constraints

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