Гноми щойно збудували своє нове підземне селище. Тепер настав час спланувати мережу залізниць, яка в ньому діятиме.

Селище складається з $N$ перехресть і $N - 1$ тунелів, що їх з'єднують. Тунелі побудовані таким чином, що від будь-якого перехрестя можна дістатися до будь-якого іншого. На кожному перехресті, яке є глухим кутом (тобто з'єднане лише одним тунелем), розташована залізнична станція.

Ваше завдання — визначити маршрути поїздів у селищі. Щоб виконати вимоги гномів, усі станції мають бути розбиті на пари (на щастя, їх парна кількість), і між кожною парою курсуватиме один поїзд найкоротшим можливим шляхом. Однак тунелі мають свої обмеження. Хоча кожен тунель має однакову довжину (рівну $1$), їхня ширина дозволяє пропустити лише обмежену кількість маршрутів.

Гноми хочуть, щоб сумарна довжина маршрутів поїздів була якомога більшою. Чи зможете ви обчислити, якою може бути максимальна довжина?

Вхідні дані

Перший рядок вхідних даних містить одне ціле число $N$, що позначає кількість перехресть у селищі.

Кожен із наступних $N - 1$ рядків містить три цілі числа $a_i$, $b_i$, $c_i$, що позначають тунель між перехрестями $a_i$ та $b_i$. Значення $c_i$ — це верхня межа кількості маршрутів, які можуть проходити через цей тунель.

Вихідні дані

У першому і єдиному рядку виведіть одне ціле число, що позначає максимальну сумарну довжину шляхів між вибраними парами станцій.

Якщо розбити станції на пари з дотриманням обмежень неможливо, виведіть $-1$.

Обмеження

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, усі перехрестя зв'язані, а кількість станцій (тобто глухих кутів) є парною.

Приклади

Вхідні дані 1

10
1 2 2
2 3 1
3 4 3
5 1 1
6 1 2
7 2 3
8 3 2
9 3 1
10 4 7

Вихідні дані 1

10

Примітка

У першому прикладі з'єднання станцій на перехрестях $5\text{--}9$, $6\text{--}7$ та $8\text{--}10$ дає сумарну довжину маршрутів поїздів, що дорівнює $4 + 3 + 3 = 10$.

Вхідні дані 2

5
1 2 3
1 3 1
1 4 0
1 5 2

Вихідні дані 2

-1