У Юллихского инженерно-технологического института (YETI), расположенного на севере Сноубловии, есть две проблемы: снег и деньги. В частности, у них слишком много первого и недостаточно второго. Каждую зиму (а также осень и весну, если на то пошло) кампус покрывается снегом, а тротуары, соединяющие здания кампуса, становятся непроходимыми. Чтобы продолжить работу, YETI необходимо расчистить от снега тротуары, соединяющие здания кампуса. Поскольку бюджет является проблемой, эти тротуары представляют собой минимальный набор, позволяющий создать путь между любыми двумя зданиями. На деньги, сэкономленные за счет отказа от строительства новых тротуаров, YETI купила два снегоочистителя. Чтобы с их помощью расчистить снег, два сотрудника выносят два снегоуборщика из зданий (или здания), в котором они хранятся, и толкают их по тротуарам, расчищая снег. Каждый тротуар необходимо пересечь хотя бы один раз. Каждый снегоочиститель после завершения работы хранится в здании, рядом с которым он находится в данный момент (а во время следующего снегопада снегоочистители будут двигаться в обратном направлении --- и так в течение одиннадцати месяцев снежного сезона). Техническая бригада YETI хочет выбрать здания для хранения снегоочистителей и спроектировать маршруты, по которым они будут перемещаться, таким образом, чтобы свести к минимуму общее расстояние, которое две машины пройдут на морозе (чтобы защитить как ценное оборудование, так и сотрудников от замерзания). Обратите внимание, что маршруты могут включать движение по уже расчищенным тротуарам, как показано на рисунке J.1, где показано оптимальное решение для схемы тротуара из примера входных данных 1. \includegraphics{https://static.eolymp.com/content/e5/e5h26n8m1h11b6fo50tlvhm8bk.gif} YETI попросили свой отдел компьютерных наук разобраться в этом, но он был уничтожен во время Великой метели 2006 года, поэтому они обратились к Вам за помощью. \InputFile В первой строке записано целое число $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)$. \OutputFile Выведите минимальное общее расстояние, которое должны пройти снегоочистители, чтобы убрать снег со всех тротуаров.