Сніг не проблема

У Юлліхському інженерно-технологічному інституті (YETI), розташованому на півночі Сноубловії, є дві проблеми: сніг і гроші. Зокрема, у них занадто багато першого і недостатньо другого. Кожної зими (а також восени і навесні, якщо на те пішло) кампус вкривається снігом, а тротуари, що з'єднують будівлі кампусу, стають непрохідними. Щоб продовжити роботу, YETI необхідно розчистити від снігу тротуари, що з'єднують будівлі кампусу. Оскільки бюджет є проблемою, ці тротуари представляють собою мінімальний набір, що дозволяє створити шлях між будь-якими двома будівлями.

На гроші, зекономлені за рахунок відмови від будівництва нових тротуарів, YETI купила два снігоочисники. Щоб з їх допомогою розчистити сніг, два співробітники виносять два снігоочисники з будівель (або будівлі), в якому вони зберігаються, і штовхають їх по тротуарах, розчищаючи сніг. Кожен тротуар необхідно перетнути хоча б один раз. Кожен снігоочисник після завершення роботи зберігається в будівлі, поруч з якою він знаходиться в даний момент (а під час наступного снігопаду снігоочисники будуть рухатися у зворотному напрямку — і так протягом одинадцяти місяців снігового сезону).

Технічна бригада YETI хоче вибрати будівлі для зберігання снігоочисників і спроектувати маршрути, за якими вони будуть переміщатися, таким чином, щоб звести до мінімуму загальну відстань, яку дві машини пройдуть на морозі (щоб захистити як цінне обладнання, так і співробітників від замерзання). Зверніть увагу, що маршрути можуть включати рух по вже розчищених тротуарах, як показано на рисунку J.1, де показано оптимальне рішення для схеми тротуару з прикладу вхідних даних 1.

YETI попросили свій відділ комп'ютерних наук розібратися в цьому, але він був знищений під час Великої хуртовини 2006 року, тому вони звернулися до Вас за допомогою.

Вхідні дані

У першому рядку записано ціле число $n(4\le n\le 10^5)$ — кількість будівель у кампусі YETI. Будівлі пронумеровані від $1$ до $n$. У кожному з наступних $n-1$ рядків записані три цілі числа $a$, $b$ і $d$, що вказують на наявність тротуару між будівлями $a$ і $b(1\le a,b\le n,a\ne b)$ довжини $d(1\le d\le 500)$.

Вихідні дані

Виведіть мінімальну загальну відстань, яку повинні пройти снігоочисники, щоб прибрати сніг з усіх тротуарів.

Приклади