# 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