Ближайшая больница

Дано n городов, соединённых m двунаправленными дорогами. Каждый город может быть либо обычным городом, либо городом, в котором есть больница. Ваша задача — для каждого города определить расстояние до ближайшей больницы, используя эту дорожную сеть.

Входные данные

Первая строка содержит два целых числа, разделённые пробелом, — n и m (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5), где n — количество городов, а m — количество дорог.

Во второй строке находятся n целых чисел h_1, h_2, ..., h_n (каждое число равно 0 или 1), где h_i показывает, есть ли больница в городе i. Если h_i равно 1, значит в городе i расположена больница.

Затем следует m строк, в каждой из которых указаны три целых числа u_i, v_i и w_i (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 10^9), описывающие двунаправленную дорогу длиной wi между городами ui и vi.

Гарантируется, что все города соединены в одну сеть и по крайней мере один город обладает больницей.

Выходные данные

Выведите одну строку, содержащую n чисел, разделённых пробелами. Каждое число соответствует расстоянию от города i до ближайшей больницы.

Примеры