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

Примітка

Мережа доріг із прикладу має такий вигляд: