Містер В

Друзі подарували Містеру В $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$, після чого з'єднати бусину з номером $3$ з бусиною з номером $5$ червоною ниткою, потім роз'єднати бусини з номерами $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$ бали): без додаткових обмежень.