Гномы только что построили свою новую подземную деревню. Теперь пришло время спланировать сеть железных дорог, которая будет в ней действовать.

Деревня состоит из $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