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

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

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

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

Первая строка содержит целые числа $$$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-(n-1)$$$ строк по одному целому числу в каждой: $$$E_{max}(c_i)$$$ для $$$i$$$-го Коридора $$$c_i$$$ из входных данных, среди тех, которые не входят в План Далеков (минимальное остовное дерево)

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

Если $$$m = n-1$$$, то вам следует ничего не выводить.