J. Отправьте Дурака Дальше! (простая)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Друг Хайди Дженни просит ее доставить важное письмо их общему другу. Поскольку Дженни ирландка, Хайди считает, что это может быть шутка. Точнее, она подозревает, что сообщение, которое она попросила доставить, гласит: «Отправьте дурака дальше!», и, читая его, получатель попросит Хайди передать то же сообщение другому другу (общему для получателя и Хайди), и так далее.

Хайди считает, что ее друзья хотят избежать неловких ситуаций, поэтому она не сможет дважды посетить одного и того же человека (включая Дженни). Она также знает, какова стоимость путешествий между любыми двумя друзьями, которые знают друг друга. Она хочет знать: какова максимальная сумма денег, которую она потратит на путешествие, если это действительно шутка?

У Хайди есть n друзей, пронумерованных от 0 до n - 1, и их дружеские связи образуют дерево. Другими словами, каждые двое из ее друзей a и b знают друг друга, возможно, косвенно (то есть существует последовательность друзей, начинающаяся с a и заканчивающаяся b такая, что каждые два последовательных друга в этой последовательности знают друг друга напрямую). Есть ровно n - 1 пара друзей, которые знают друг друга напрямую.

Дженни имеет номер 0.

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

В первой строке следует целое число n (3 ≤ n ≤ 100) — количество друзей.

Каждая из следующих n - 1 строк содержит по три разделенных пробелом целых числа u, v и c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 104), что означает, что u и v являются друзьями (знают друг друга напрямую) и стоимость путешествия между u и v равна c.

Гарантируется, что дружеские связи из входных данных формируют дерево.

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

Выведите единственное число — максимальная сумма денег, которую Хайди может потратить на путешествия между друзьями.

Примеры
Входные данные
4
0 1 4
0 2 2
2 3 3
Выходные данные
5
Входные данные
6
1 2 3
0 2 100
1 4 2
0 3 7
3 5 10
Выходные данные
105
Входные данные
11
1 0 1664
2 0 881
3 2 4670
4 2 1555
5 1 1870
6 2 1265
7 2 288
8 7 2266
9 2 1536
10 6 3378
Выходные данные
5551
Примечание

Во втором примере наихудший сценарий выглядит следующим образом: Дженни отправляет Хайди к другу, помеченному номером 2 (Хайди расходует на это 100). Потом друг 2 отправляет Хайди к другу 1 (Хайди тратит на это 3). Затем 1 направляет ее к другу 4 (Хайди расходует на это 2).