Octagon отвечает за множество стратегически важных объектов: ракетные шахты, радары, столовые, учреждения для ветеранов, склады обмундирования, … Крайне важно обеспечить безопасность сети соединений между этими объектами, но, с другой стороны, угроза этой сети должна быть минимальной. Для каждой двусторонней дороги, соединяющей разные объекты, определён коэффициент угрозы нападения (обычно называемый просто коэффициентом). Johnny, недавно принятый на работу в Octagon, даже посреди ночи может вычислить подмножество дорог, минимизирующее сумму коэффициентов и при этом позволяющее перемещаться между любой парой объектов; дорогу, входящую хотя бы в одно такое подмножество, назовём ключевой.

Однако ничто нельзя считать неизменным: коэффициенты могут меняться. В рамках ежегодной оценки Octagon решил для каждой дороги вычислить наибольшее значение $x$, такое что при установке её коэффициента равным $x$ (и сохранении всех остальных коэффициентов прежними) эта дорога является ключевой. Задача поручена Johnny, который не может ошибиться в столь важном деле.

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

Первая строка ввода содержит два целых числа $n$ и $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$), разделённых одним пробелом, — соответственно количество объектов под надзором Octagon и количество двусторонних дорог между ними. Объекты пронумерованы последовательными натуральными числами от $1$ до $n$.

В каждой из следующих $m$ строк находятся три целых числа $a$, $b$ и $c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$), разделённые одним пробелом, описывающие двустороннюю дорогу между объектами $a$ и $b$ с коэффициентом $c$. Каждая неупорядоченная пара $\{a,b\}$ встречается не более одного раза.

Существующие дороги всегда позволяют перемещаться между любыми двумя объектами.

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

Выведите $m$ строк, по одной для каждой дороги из ввода, в том же порядке. В строке для конкретной дороги выведите одно натуральное число — максимальное значение, такое что после изменения коэффициента этой дороги на это значение (при неизменных остальных коэффициентах) она является ключевой. Если это значение больше $10^9$ или может быть сколь угодно большим, выведите $10^9$.

Примеры

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

6 7
1 2 2
2 3 1
3 4 0
1 4 3
3 5 20
4 5 8
3 6 14

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

3
3
3
2
8
20
1000000000

Примечание

Дорожная сеть из примера выглядит следующим образом: