Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 70%)

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

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

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

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

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

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

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

Пример

INPUT.TXTOUTPUT.TXT
16 7
1 2 2
2 3 3
1 3 1
3 4 1
4 5 2
5 3 1
3 6 1
2 5 6 8 -1

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru