Безопасное мореплавание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, океан опасен не только возможными штормами, но и множеством быстрых течений, которые могут унести лодку очень далеко от ожидаемого конца маршрута. Моана и Мауи прекрасно об этом знают, более того, они знают, что всего в океане $$$m$$$ таких течений между $$$n$$$ различными точками.

Течение номер $$$i$$$ соединяет точки $$$u_i$$$ и $$$v_i$$$, и обладает мощностью $$$w_i$$$. В отличие от нашего мира, течения периодически меняют свое направление на противоположное, так что будем считать их двунаправленными.

Чтобы быстрее добраться до острова Те Фити, Моана и Мауи планируют использовать какие-то из течений в своем плавании. Но пока они еще не знают, где находится остров, они планируют выбрать набор течений, по которым можно добраться из любой точки в другую, при этом обладающий минимальной суммарной мощностью.

И все было бы просто, если бы на этом все закончилось, но поскольку надо торопиться, герои могут попросить богов океана изменить мощность любого течения на произвольное целое число от $$$1$$$ до $$$10^9$$$.

Определите для каждого течения $$$f$$$ максимальную мощность $$$p_f$$$ такую, что если сделать мощность $$$f$$$ равной $$$p_f$$$, а остальные течения оставить без изменений, будет существовать искомый набор течений, включающий в себя $$$f$$$.

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

В первой строке ввода даны целые числа $$$n$$$ и $$$m$$$ — количество точек, между которыми протекают течения, и количество течений соответственно ($$$1 \le n \le 10^5$$$; $$$1 \le m \le 4 \cdot 10^5$$$). Гарантируется, что по данным течениям можно добраться из любой точки в любую.

Затем перечислены описания течений: в $$$i$$$-й из следующих $$$m$$$ строк даны числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$; $$$1 \le w_i \le 10^9$$$).

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

Выведите по одному на каждой строке $$$m$$$ целых чисел $$$f_1$$$, $$$f_2$$$, ..., $$$f_m$$$.

Примеры

Входные данные
2 1
1 2 1000
Выходные данные
1000000000
Входные данные
3 3
1 2 10
2 3 9
3 1 11
Выходные данные
11
11
10
Входные данные
5 8
1 2 1
2 3 2
1 4 6
3 5 2
1 5 3
2 4 1
4 5 8
1 3 4
Выходные данные
3
3
1
3
2
6
2
2

Примечание

В первом примере течение единственное, поэтому при любой мощности оно будет включено в искомый набор.

Во втором примере для каждого течения ответ — это максимум из мощностей двух оставшихся течений (тогда два течения с одинаковой мощностью будут взаимозаменяемы).