Интенсивность движения

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

Ваша задача — для каждого города i определить минимальную возможную загруженность при движении от города 1 к городу i. Под загруженностью пути подразумевается максимальная интенсивность движения на всём его протяжении.

Ввод

В первой строке находятся два целых числа n и m (разделённые пробелом) (), обозначающие количество городов и количество дорог соответственно.

В следующих m строках каждая строка содержит три целых числа и (также разделённые пробелами) (). Они описывают дорогу между городами и с интенсивностью движения .

Вывод

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

Примеры