Интенсивность движения
Существует
n городов, соединённых m дорогами. Каждая дорога представляет собой транспортный маршрут и имеет показатель интенсивности движения , который указывает уровень загруженности.Ваша задача — для каждого города
i определить минимальную возможную загруженность при движении от города 1 к городу i. Под загруженностью пути подразумевается максимальная интенсивность движения на всём его протяжении.Ввод
В первой строке находятся два целых числа
n и m (разделённые пробелом) (), обозначающие количество городов и количество дорог соответственно.В следующих
m строках каждая строка содержит три целых числа и (также разделённые пробелами) (). Они описывают дорогу между городами и с интенсивностью движения .Вывод
Выведите одну строку, содержащую
n-1 целых чисел, разделённых пробелом, где i-е число соответствует минимально возможной загруженности пути от города 1 до города i+1.Примеры
Входные данные | Выходные данные |
5 5
1 2 5
1 3 2
4 5 10
4 3 6
1 5 9 | 5 2 6 9 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB