Krasnoludy właśnie zbudowały swoją nową podziemną wioskę. Teraz nadszedł czas, aby zaplanować sieć kolei, która będzie w niej funkcjonować.

Wioska składa się z $N$ skrzyżowań oraz $N - 1$ łączących je tuneli. Tunele zostały zbudowane w taki sposób, że z każdego skrzyżowania można dotrzeć do każdego innego. Na każdym skrzyżowaniu będącym ślepym zaułkiem (co oznacza, że wychodzi z niego tylko jeden tunel) znajduje się stacja kolejowa.

Twoim zadaniem jest wyznaczenie tras pociągów w wiosce. Aby spełnić wymagania krasnoludów, wszystkie stacje muszą zostać połączone w pary (na szczęście jest ich parzysta liczba), a między każdą parą będzie kursował jeden pociąg, jadący najkrótszą możliwą ścieżką. Tunele mają jednak swoje ograniczenia. Chociaż każdy tunel ma taką samą długość (równą $1$), ich szerokość pozwala na przejazd tylko ograniczonej liczby tras.

Krasnoludy chcą, aby sumaryczna długość tras pociągów była jak największa. Czy potrafisz obliczyć, jaka może być maksymalna długość?

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $N$, oznaczającą liczbę skrzyżowań w wiosce.

Każdy z kolejnych $N - 1$ wierszy zawiera trzy liczby całkowite $a_i$, $b_i$, $c_i$, opisujące tunel między skrzyżowaniami $a_i$ oraz $b_i$. Wartość $c_i$ oznacza górne ograniczenie na liczbę tras, które mogą przebiegać przez ten tunel.

Wyjście

W pierwszym i jedynym wierszu wypisz jedną liczbę całkowitą oznaczającą maksymalną sumaryczną długość ścieżek pomiędzy wybranymi parami stacji.

Jeśli nie da się połączyć stacji w pary z zachowaniem ograniczeń, wypisz $-1$.

Ograniczenia

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, wszystkie skrzyżowania są połączone, a liczba stacji (tj. ślepych zaułków) jest parzysta.

Przykłady

Wejście 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

Wyjście 1

10

Uwaga

W pierwszym przykładzie połączenie stacji na skrzyżowaniach $5\text{--}9$, $6\text{--}7$ oraz $8\text{--}10$ daje sumaryczną długość tras pociągów równą $4 + 3 + 3 = 10$.

Wejście 2

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

Wyjście 2

-1