393. Два центра

Не решаласьСредняя

Дано взвешенное дерево T T . Назовем 2-радиусом минимальную величину r r , для которой существуют 2 смежные вершины u u и v v , что для любой вершины w w верно неравенство:

m i n ( d i s t a n c e ( u , w ) , d i s t a n c e ( v , w ) ) ≤ r min(distance(u, w), distance(v, w)) \le r

Формат ввода

В первой строке записано единственное число n n − - количество вершин в дереве ( 3 ≤ n ≤ 2222 3 \le n \le 2222 ).

Далее в n − 1 n-1 строке идут описания ребер в формате a a , b b , c c ( 1 ≤ a < b ≤ n 1 \le a < b \le n , 1 ≤ c ≤ 500   000 1 \le c \le 500\ 000 ) − - между вершинами a a и b b есть ребро длины c c .

Формат вывода

В единственной строке выведите значение 2-радиуса.

Ограничения

Ограничение времени
2 с
Ограничение памяти
256 МБ

Примеры

Пример 1

Ввод
3
1 2 5
2 3 10
Вывод
5

Пример 2

Ввод
5
1 2 1
1 3 1
1 4 1
1 5 1
Вывод
1

Пример 3

Ввод
10
1 2 16
2 3 18
1 4 49
1 5 29
5 6 20
3 7 29
6 8 34
7 9 9
9 10 32
Вывод
88

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти