406420: GYM102399 D Дороги в стране

D. Дороги в странеограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

В некоторой стране есть $$$n$$$ городов, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Столица этой страны расположена в городе с номером $$$1$$$. Некоторые пары городов в этой стране соединены дорогами с односторонним движением, при этом для каждой пары городов $$$u$$$ и $$$v$$$ есть не более одной дороги, ведущей из города $$$u$$$ в город $$$v$$$, однако наличие дороги из города $$$u$$$ в город $$$v$$$ не запрещает существование дороги из города $$$v$$$ в город $$$u$$$. Для каждой дороги известно, груз какого максимального веса можно по ней перевозить. Требуется для каждого города определить максимальный вес груза, который можно доставить из него в столицу.

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

В первой строке содержатся два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 10^5$$$, $$$0 \le m \le 10^6$$$) — количество городов и дорог в стране, соответственно.

В следующих $$$m$$$ строках содержатся описания дорог. Описание дороги состоит из трёх целых чисел $$$u$$$, $$$v$$$ и $$$w$$$ ($$$1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^9$$$), описывающих дорогу с односторонним движением из города с номером $$$u$$$ в город с номером $$$v$$$, по которой можно перевозить грузы весом не более $$$w$$$. Гарантируется, что для каждой пары городов $$$u$$$ и $$$v$$$ существует не более одной дороги из $$$u$$$ в $$$v$$$.

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

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

ПримерыВходные данные

4 4
1 2 3
2 3 6
3 4 2
4 1 1

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

1
1
1

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

4 5
2 3 3
3 1 7
2 1 2
2 4 9
4 1 1

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

3
7
1

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

3 2
2 1 2
1 3 2

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

2
-1

Примечание

В первом примере есть только одна дорога, заканчивающаяся в столице, и по ней нельзя везти грузы весом более $$$1$$$, при этом из всех городов можно доехать до столицы по дорогам. Таким образом, из всех городов можно привезти в столицу груз весом не более $$$1$$$.

Во втором примере из города $$$2$$$ в город $$$1$$$ можно перевезти груз весом $$$3$$$ следующим образом: проехать из города $$$2$$$ в город $$$3$$$ по дороге, по которой можно везти грузы весом не более $$$3$$$, а затем из города $$$3$$$ в столицу (город $$$1$$$) по дороге, по которой можно везти грузы весом не более $$$7$$$. Из города $$$3$$$ в город $$$1$$$ можно доставить груз весом $$$7$$$ по прямой дороге, соединяющей эти города. Аналогично, из горда $$$4$$$ в город $$$1$$$ можно перевезти груз весом $$$1$$$ по дороге, соединяющей эти города напрямую.

В третьем примере из города $$$3$$$ в столицу доехать нельзя.