F. Дороги в королевстве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В королестве К. есть 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-й дороги. Никакая дорога не соединяет город сам с собой, никакие две дороги не соединяют одну и ту же пару городов.

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

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

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

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