Містер В#10503
Друзі подарували Містеру В бусин пронумерованих цілими числами від до . Герой з'єднав буси використовуючи (n-1) ниток так, щоб утворилось намисто. Оскільки Містер В — програміст, намисто має деревоподібну структуру.
Будував намисто Містер В наступним чином: спочатку він вибрав деяку початкову бусину, після чого (n-1) раз додавав одну бусину до свого намиста. Бусину він міг додати одним з наступних способів: герой або вибирав деяку бусину, що вже належить намисту та з'єднував її з бусиною, що ще не належить намисту червоною ниткою, або ж він вибирав деяку пару бусин з намиста що з'єднані червоною ниткою після чого роз'єднував їх та з'єднував синьою ниткою кожну з них з бусиною, яку зараз додає до намиста.
Нитки, що з'єднують буси намиста, можуть мати різні довжини.
Містер В записав структуру намиста, після чого подарував його Місіс В. Однак він забув кольори ниток в намисті. Допоможіть йому дізнатись максимально можливу суму довжин синіх ниток намиста, адже саме це значення його дуже зацікавило.
Перший рядок містить одне ціле число (1\le n\le 2\cdot 10^5) — кількість бусин намиста.
Кожен з наступних n-1 рядків містить по три цілі числа , та (1\le u<v\le n, 1\le l\le 10\,000) — номери бусин, які з'єднує відповідна нитка, та її довжина.
Виведіть одне ціле число — максимально можливу суму довжин синіх ниток намиста.
Приклад 1
Приклад 2
У першому прикладі Містер В міг почати будувати намисто з бусини з номером , після чого з'єднати бусину з номером з бусиною з номером червоною ниткою, потім роз'єднати бусини з номерами і та з'єднати бусини з номерами і та і синіми нитками, потім з'єднати бусини з номерами і червоною ниткою і останнім кроком з'єднати бусини з номерами і червоною ниткою. Таким чином сума довжин синіх ниток буде рівною .
( балів): 1\le n\le 10;
( балів): 1\le n\le 200;
( балів): 1\le n\le 10000;
( бали): без додаткових обмежень.