Problems
Містер В
Містер В
Друзі подарували Містеру В $n$ бусин пронумерованих цілими числами від $1$ до $n$. Герой з'єднав буси $(n-1)$-ою ниткою так, щоб утворилось намисто. Оскільки Містер В, програміст то намисто має деревоподібну структуру.
Будував намисто Містер В наступним чином: спочатку він вибрав деяку початкову бусину, після чого $(n-1)$ раз додавав одну бусину до свого намиста. Бусину він міг додати одним з наступних способів: герой або вибирав деяку бусину, що вже належить намисту та з'єднував її з бусиною, що ще не належить намисту червоною ниткою, або ж він вибирав деяку пару бусин з намиста що з'єднані червоною ниткою після чого роз'єднував їх та з'єднував синьою ниткою кожну з них з бусиною, яку зараз додає до намиста.
Нитки, що з'єднують буси намиста, можуть мати різні довжини.
Містер В записав структуру намиста, після чого подарував його Місіс В. Але от халепа~--- герой забув кольори ниток в намисті. Допоможіть йому дізнатись максимально можливу суму довжин синіх ниток намиста, адже саме це значення його дуже зацікавило.
\InputFile
Перший рядок містить одне ціле число $n$ ($1\le n\le 2\cdot 10^5$)~--- кількість бусин намиста.
Кожен з наступних $n-1$ рядків містить по три цілі числа $u$,$v$ та $l$ ($1\le u<v\le n$, $1\le l\le 10\,000$)~--- номери бусин, які з'єднує відповідна нитка, та її довжина.
\OutputFile
Виведіть одне ціле число~--- максимально можливу суму довжин синіх ниток намиста.
\Note
У першому прикладі Містер В міг почати будувати намисто з бусини з номером $3$, після чого з'єднати бусину з номером $3$ з бусиною з номером $5$ червоною ниткою, потім роз'єднати бусини з номерами $3$ і $5$ та з'єднати бусини з номерами $1$ і $3$ та $1$ і $5$ синіми нитками, потім з'єднати бусини з номерами $1$ і $2$ червоною ниткою і останнім кроком з'єднати бусини з номерами $1$ і $4$ червоною ниткою. Таким чином сума довжин синіх ниток буде рівною $60$.
\Scoring
\begin{enumerate}
\item ($13$ балів): $1\le n\le 10$;
\item ($15$ балів): $1\le n\le 200$;
\item ($29$ балів): $1\le n\le 10000$;
\item ($43$ бали): без додаткових обмежень.
\end{enumerate}
Input example #1
5 1 2 10 1 3 40 1 4 15 1 5 20
Output example #1
60
Input example #2
10 4 10 2 1 2 21 1 3 13 6 7 1 7 9 5 2 4 3 2 5 8 1 6 55 6 8 34
Output example #2
140