Друзі подарували Містеру В n бусин пронумерованих цілими числами від 1 до n. Герой з'єднав буси (n−1)-ою ниткою так, щоб утворилось намисто. Оскільки Містер В, програміст то намисто має деревоподібну структуру.
Будував намисто Містер В наступним чином: спочатку він вибрав деяку початкову бусину, після чого (n−1) раз додавав одну бусину до свого намиста. Бусину він міг додати одним з наступних способів: герой або вибирав деяку бусину, що вже належить намисту та з'єднував її з бусиною, що ще не належить намисту червоною ниткою, або ж він вибирав деяку пару бусин з намиста що з'єднані червоною ниткою після чого роз'єднував їх та з'єднував синьою ниткою кожну з них з бусиною, яку зараз додає до намиста.
Нитки, що з'єднують буси намиста, можуть мати різні довжини.
Містер В записав структуру намиста, після чого подарував його Місіс В. Але от халепа — герой забув кольори ниток в намисті. Допоможіть йому дізнатись максимально можливу суму довжин синіх ниток намиста, адже саме це значення його дуже зацікавило.
Перший рядок містить одне ціле число n (1≤n≤2⋅105) — кількість бусин намиста.
Кожен з наступних n−1 рядків містить по три цілі числа u,v та l (1≤u<v≤n, 1≤l≤10000) — номери бусин, які з'єднує відповідна нитка, та її довжина.
Виведіть одне ціле число — максимально можливу суму довжин синіх ниток намиста.
У першому прикладі Містер В міг почати будувати намисто з бусини з номером 3, після чого з'єднати бусину з номером 3 з бусиною з номером 5 червоною ниткою, потім роз'єднати бусини з номерами 3 і 5 та з'єднати бусини з номерами 1 і 3 та 1 і 5 синіми нитками, потім з'єднати бусини з номерами 1 і 2 червоною ниткою і останнім кроком з'єднати бусини з номерами 1 і 4 червоною ниткою. Таким чином сума довжин синіх ниток буде рівною 60.
(13 балів): 1≤n≤10;
(15 балів): 1≤n≤200;
(29 балів): 1≤n≤10000;
(43 бали): без додаткових обмежень.