Дороги

У країні X є n міст, позначених числами від 1 до n. Дорожня мережа складається з n - 1 двосторонніх звичайних доріг, кожна з яких з'єднує два міста і має фіксовану довжину, виражену натуральним числом. Кожна з цих доріг була побудована в різний час, і дорожня мережа спроектована так, що існує маршрут між будь-якими двома містами, який може бути або звичайною дорогою, або проходити через інші міста, використовуючи звичайні дороги. Оскільки автомобільний рух постійно зростає, уряд планує замінити звичайні дороги двосторонніми автомагістралями. Магістралі між містами будуть побудовані за такими правилами:

• Автомагістраль буде побудована лише між двома містами, між якими вже існує пряма дорога. Автомагістраль замінює звичайну дорогу.

• Лише одна автомагістраль може будуватися в один момент часу.

• Автомагістралі будуть побудовані в тому ж порядку, в якому були побудовані звичайні дороги (врахуйте, що всі звичайні дороги були побудовані в різний час).

Назвемо "районом" країни будь-яку максимальну підмножину міст і звичайних доріг (без автомагістралей) початкової дорожньої мережі, таку, що між будь-якими двома містами в ній є маршрут, використовуючи лише звичайні дороги. Після будівництва кожної магістралі рівно одна область країни розділяється на дві області (можливо, що одна або обидві нові зони складаються з одного міста без доріг). "Простий маршрут" - це маршрут, який може проходити через місто не частіше одного разу. Після будівництва кожної нової автомагістралі уряд країни X хотів би дізнатися довжину найдовших простих маршрутів між двома містами в кожній з двох нових областей.

Напишіть програму, яка відповість на ці питання.

Вхідні дані

Перша рядок містить одне натуральне число n (1 ≤ n ≤ 500000) - кількість міст у країні X.

Наступні n - 1 рядків описують існуючу мережу доріг перед створенням автомагістралей. Кожен рядок містить три натуральних числа - перші два позначають номери міст, між якими є звичайна дорога, а третє - її довжина.

Звичайні дороги задані в тому ж порядку, в якому вони були побудовані.

Довжини всіх звичайних доріг знаходяться між 1 і 1000 включно.

Вихідні дані

Виведіть n - 1 рядків - в i-му рядку виведіть два цілих числа, розділених пробілом – довжини найдовших шляхів (використовуючи лише звичайні дороги) між двома містами в кожній з двох нових областей, утворених після побудови i-ї автомагістралі. Числа слід виводити в невозростаючому порядку.

Приклади

Примітка

Позначимо через {t[1], t[2], ..., t[k]} область, що містить міста t[1], t[2], ..., t[k] і звичайні дороги між ними.

1. Перед побудовою першої автомагістралі:

Існує лише одна область {1, 2, 3, 4, 5}.

1. Після побудови першої автомагістралі між містами 1 і 2:

Країна розбивається на дві області - {1, 5} і {2, 3, 4}. Довжини найдовших шляхів між містами в кожній з них: в {1, 5} - 3 (між містами 1 і 5); в {2, 3, 4} - 3 (між містами 3 і 4).

1. Після побудови другої автомагістралі між містами 2 і 3:

Область {2, 3, 4} розбивається на дві - {3} і {2, 4}. Довжини найдовших шляхів між містами в кожній з них 0 і 2. Виводимо їх у невозростаючому порядку!

1. Після побудови третьої автомагістралі між містами 2 і 4:

Область {2, 4} розбивається на дві - {2} і {4}. Довжини найдовших шляхів в обох областях 0.

1. Після побудови четвертої автомагістралі між містами 1 і 5:

Область {1, 5} розбивається на {1} і {5}. Довжини найдовших шляхів 0.