Будівництво шосе
Як керівник Руху за Доступне Комп'ютування (РДК), ви переконали мера побудувати нову автомагістраль у вашому місті. Сьогодні ваш щасливий день, адже ваш запит було схвалено. Проте є одна умова: ви повинні надати план найкращої магістральної артерії для будівництва, інакше цього не станеться!
У вас є карта, яка показує всі громади у вашому місті, кожна з унікальним номером, де ви можете розмістити з'їзди на автомагістраль. На карті є набір доріг між парами громад, позначених відстанями для проїзду, які ви можете вибрати для заміни на вашу автомагістраль. Використовуючи цю мережу доріг, існує рівно один маршрут від будь-якої однієї громади до іншої. Іншими словами, немає двох різних наборів доріг, які б вели вас від громади A до громади B.
Ви можете побудувати одну автомагістраль, яка буде курсувати туди і назад між будь-якими двома громадами на ваш вибір. Вона замінить унікальний набір доріг між цими двома громадами, і на кожній громаді по дорозі буде побудовано не-з'їзд. Звичайно, жителі громад, які не матимуть з'їзду, повинні будуть їхати до найближчого, щоб отримати доступ до вашої нової автомагістралі.
Ви знаєте, що довгі поїздки дуже небажані, тому ви збираєтеся побудувати автомагістраль так, щоб найдовша поїздка від будь-якої громади до найближчого з'їзду була мінімізована. Враховуючи карту вашого міста з дорогами та відстанями для проїзду, яка є найдальшою відстанню від будь-якої громади, яку доведеться проїхати, щоб дістатися до найближчого з'їзду, коли ваша нова автомагістраль буде завершена?
Вхідні дані
Вхід складається з кількох тестових випадків. Кожен тестовий випадок є описом карти міста і починається з одного рядка, що містить ціле число N (2 ≤ N ≤ 100000), кількість громад у місті. Потім слідують N-1 рядків, кожен з яких містить три цілі числа, i, j (1 ≤ i, j ≤ n), і d (1 ≤ d ≤ 10000). Кожен рядок вказує, що громади i та j з'єднані дорогою з відстанню для проїзду d. Вхід завершується одним рядком з N = 0, який не слід обробляти.
Вихідні дані
Для кожної карти міста виведіть в одному рядку найдальшу відстань від будь-якої громади до найближчого з'їзду нової автомагістралі.