Как известно, океан опасен не только возможными штормами, но и множеством быстрых течений, которые могут унести лодку очень далеко от ожидаемого конца маршрута. Моана и Мауи прекрасно об этом знают, более того, они знают, что всего в океане $$$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
В первом примере течение единственное, поэтому при любой мощности оно будет включено в искомый набор.
Во втором примере для каждого течения ответ — это максимум из мощностей двух оставшихся течений (тогда два течения с одинаковой мощностью будут взаимозаменяемы).