Доставка грибов

Леша работает в службе доставки сушеных грибов. Некоторые клиенты жалуются, что грибы доставляются слишком долго. Леша хочет проверить, не является ли это следствием неэффективной системы доставки.

Система доставки устроена следующим образом. Существуют n распределительных пунктов, между некоторыми из которых есть односторонние каналы доставки. Грибы могут быть перевезены из пункта a_i в пункт b_i за время t_i. С основной базы грибы поступают на пункт номер 1 и далее доставляются до нужного пункта по каналам доставки. Система каналов довольна сложна, так что есть несколько путей, по которым можно доставить грибы до некоторых пунктов. При этом никто не следит за тем, чтобы выбранный путь был самым коротким.

Леша хочет узнать для каждого пункта, какое максимальное время до него могут идти грибы от первого пункта при условии, что на промежуточных пунктах грибы не задерживаются.

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

В первой строке входного файла INPUT.TXT содержатся числа n и m - количество распределительных пунктов и количество каналов доставки (2 ≤ n ≤ 100, 1 ≤ m ≤ 10000). Далее следуют m троек a_i, b_i, t_i (a_i ≠ b_i, 1 ≤ t_i ≤ 100).

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

В выходной файл OUTPUT.TXT выведите n-1 число – максимальное время доставки грибов до второго, третьего, …, n-го пункта. Если грибы до пункта могут идти сколь угодно долго, выведите вместо соответствующего числа -1.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]