Олимпиадный тренинг

Задача . F. Дороги в королевстве


Задача

Темы: графы Деревья дп поиск в глубину и подобное *2500

В королестве К. есть n городов, занумерованных целыми числами от 1 до n. Города соединены n двусторонними дорогами, занумерованными целыми числами от 1 до n. i-я дорога соединяет города ui и vi и имеет длину li. Между двумя городами не бывает более одной дороги. Также не бывает дорог, которые соединяют город с самим собой.

Назовём неудобством дорог максимальное из кратчайших расстояний между всеми парами городов.

В связи с нехваткой денег было решено отказаться от одной из дорог, при этом после её удаления все города должны быть достижимы друг из друга. Вам необходимо узнать, какое минимальное неудобство дорог можно получить после отказа от одной из дорог.

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

Первая строка содержит целое число n (3 ≤ n ≤ 2·105) — количество городов и дорог.

Следующие n строк содержат описания дорог. i-я из этих строк содержит три целых числа ui, vi, li (1 ≤ ui, vi ≤ n, 1 ≤ li ≤ 109) — номера городов, которые соединяет i-я дорога, и длина i-й дороги. Никакая дорога не соединяет город сам с собой, никакие две дороги не соединяют одну и ту же пару городов.

Гарантируется, что всегда можно отказаться от одной из дорог так, чтобы все города были достижимы друг из друга.

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

Выведите одно целое число — минимально возможное неудобство дорог после отказа от одной из дорог.


Примеры
№Входные данныеВыходные данные
1 3
1 2 4
2 3 5
1 3 1 
5
2 5
2 3 7
3 1 9
4 1 8
3 5 4
4 5 5 
18

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет