D. Великая победа
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Шапур победил Валериана. Эта победа была так важна, что Шапур решил вырезать на скале сцену поражения Валериана. Теперь ему нужно было найти наилучшее место и увековечить там свою победу!

Он решил посетить все n городов Персии чтобы найти наиболее подходящую скалу. Но недавняя война утомила его, и он не хотел много путешествовать. Поэтому он хотел посетить каждый из этих n городов хотя бы один раз. При этом пройденное расстояние должно быть как можно меньше. Персидские города соединены двусторонними дорогами. Из каждого города можно дойти до любого другого, причем единственным способом.

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

Найдите расстояние, которое Шапур пройдет.

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

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

Следующие n - 1 строк содержат по 3 целых числа xi, yi и wi (1 ≤ xi, yi ≤ n, 0 ≤ wi ≤ 2 × 104). xi и yi — номера двух городов, соединенных дорогой, а wi — длина дороги.

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

Выведите одно число — минимальную длину пути Шапура.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).

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