Мистер В

Друзья подарили Мистеру В $n$ бусин, пронумерованных от $1$ до $n$. Он соединил бусины $(n-1)$ нитками, чтобы получилось ожерелье с древовидной структурой.

Мистер В создавал ожерелье следующим образом: сначала он выбирал начальную бусину, затем $(n-1)$ раз добавлял по одной бусине. Добавление происходило двумя способами: либо он соединял уже имеющуюся в ожерелье бусину с новой красной ниткой, либо разъединял пару бусин, соединённых красной ниткой, и соединял каждую из них с новой бусиной синими нитками.

Нитки, соединяющие бусины, имеют разные длины.

Мистер В записал структуру ожерелья и подарил его Миссис В, но забыл цвета ниток. Помогите ему определить максимально возможную сумму длин синих ниток в ожерелье, так как это его очень интересует.

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

Первая строка содержит одно целое число $n$ ($1\le n\le 2\cdot 10^5$) — количество бусин в ожерелье.

Каждая из следующих $n-1$ строк содержит три целых числа $u$, $v$ и $l$ ($1\le u<v\le n$, $1\le l\le 10000$) — номера бусин, соединённых ниткой, и её длина.

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

Выведите одно целое число — максимально возможную сумму длин синих ниток в ожерелье.

Примеры

Примечание

В первом примере Мистер В мог начать с бусины номер $3$, соединить её с бусиной номер $5$ красной ниткой, затем разъединить их и соединить синими нитками бусины $1$ и $3$, а также $1$ и $5$. Затем он соединяет красной ниткой бусины $1$ и $2$, и в последнем шаге соединяет красной ниткой бусины $1$ и $4$. Таким образом, сумма длин синих ниток будет равна $60$.

Оценивание

1. ($13$ баллов): $1\le n\le 10$;

2. ($15$ баллов): $1\le n\le 200$;

3. ($29$ баллов): $1\le n\le 10000$;

4. ($43$ балла): без дополнительных ограничений.