O Hospital Mais Próximo

Existem n cidades, conectadas por m estradas bidirecionais. Cada cidade pode ser uma cidade normal ou uma cidade que possui um hospital. A sua tarefa é determinar, para cada cidade, qual é o hospital mais próximo com base na rede de estradas.

Entrada

A primeira linha contém dois inteiros separados por espaço, n e m ($1 \le n \le 10^5, 1 \le m \le 10^5$), representando o número de cidades e o número de estradas, respetivamente.

A segunda linha contém n inteiros separados por espaço h_1, h_2, ..., h_n (0 ou 1), onde h_i indica se a cidade i possui hospital. Se h_i for 1, então a cidade i tem um hospital.

As próximas m linhas contêm, cada uma, três inteiros separados por espaço u_i, v_i e w_i ($1 \le ui, vi \le n$, $1 \le wi \le 10^9$), que representam uma estrada bidirecional ligando as cidades ui** e **vi**, com comprimento **wi**.

Garante-se que todas as cidades estão conectadas e que existe pelo menos um hospital.

Saída

Escreva numa única linha n inteiros separados por espaço, onde o i-ésimo inteiro corresponde à distância do hospital mais próximo da cidade i.

Exemplos