Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

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

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

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ