E3. Вторжение Далеков (сложная)
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

С вашей помощью Хайди подготовила план размещения ловушки и защиты. Однако внезапно из ТАРДИС выпрыгнул Доктор и сказал ей, что он шпионил за подготовкой Далеков, и что их больше, чем когда-либо. Отчаянные времена требует отчаянных мер, поэтому Хайди собирается рискнуть и встретится с Далеками и что она рассмотрит вариант размещения ловушки вдоль любого Коридора.

Это означает что ей опять нужна ваша помощь с вычислением $$$E_{max}(c)$$$ — наибольшего $$$e \le 10^9$$$, такого что если мы сменим требуемый уровень энергии у $$$c$$$ на $$$e$$$, то Далеки возможно воспользуются $$$c$$$ в своём вторжении. Теперь нужно вычислить эту функцию для всех Временных Коридоров.

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

Первая строка содержит целые числа $$$n$$$ и $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$n - 1 \leq m \leq 10^6$$$) — количество точек и количество коридоров.

Каждая из следующих $$$m$$$ строк содержит точки $$$a$$$, $$$b$$$ и уровень энергии $$$e$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$, $$$0 \leq e \leq 10^9$$$).

Гарантируется, что ни одна пара $$$\{a, b\}$$$ не повторяется и что граф является связным. Не гарантируется, что все уровни энергии $$$e$$$ различны или что минимальное остовное дерево уникально.

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

Выведите $$$m$$$ целых чисел: для каждого $$$i$$$, $$$E_{max}(c_i)$$$ для Коридора $$$c_i$$$ из входных данных.

Пример
Входные данные
3 3
1 2 8
2 3 3
3 1 4
Выходные данные
4
8
8