Одним декабрьским утром Макс получил необычное письмо. Оказалось, что его помощь понадобилась не кому-нибудь, а самому Деду Морозу! Действительно, скоро Новый год, и нужно будет успеть доставить подарки детям в $$$N$$$ городах нашей страны. Резиденция Деда Мороза, откуда он будет развозить подарки, расположена в городе $$$1$$$.
Выяснилось, что Дед Мороз — личность известная, влиятельная и современная, поэтому передвижение на санях он давно оставил в прошлом, а теперь путешествует с помощью чартерных самолётов.
Всего к услугам Деда Мороза есть $$$M$$$ рейсов, $$$i$$$-й из которых может отправиться из города $$$A_i$$$ в город $$$B_i$$$ (но не наоборот) и долетит за $$$T_i$$$ минут. Кроме того, Дед Мороз всё-таки волшебник, поэтому он может поменять местами города вылета и прилёта у любого рейса, но только у одного.
Сейчас Дед Мороз попросил Макса определить, за какое минимальное количество минут он сможет добраться из своей резиденции в тот или иной город. Обратите внимание, что на маршруте до каждого города Дед Мороз может один раз использовать своё волшебство (он может применять его к различным рейсам при путешествии в различные города).
Помогите Максу составить оптимальное расписание полётов для Деда Мороза.
Выходные данные
Выведите $$$(N - 1)$$$ целое число — минимальное количество минут, за которое Дед Мороз сможет добраться из города $$$1$$$ в города 2, 3, ..., $$$N$$$. Если Дед Мороз не сможет добраться до некоторого города, соответствующее число должно быть равно $$$0$$$.