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.