Các chú lùn vừa xây dựng xong ngôi làng ngầm mới của mình. Bây giờ là lúc lên kế hoạch cho mạng lưới đường sắt sẽ hoạt động bên trong đó.

Ngôi làng bao gồm $N$ giao lộ và $N - 1$ đường hầm kết nối chúng. Các đường hầm đã được xây dựng sao cho có thể đi từ bất kỳ giao lộ nào đến bất kỳ giao lộ nào khác. Tại mỗi giao lộ là ngõ cụt (nghĩa là chỉ được kết nối bởi một đường hầm duy nhất), có một nhà ga tàu hỏa.

Nhiệm vụ của bạn là xác định các tuyến đường cho tàu hỏa trong làng. Để đáp ứng yêu cầu của các chú lùn, tất cả các nhà ga phải được ghép cặp (may mắn thay, có một số chẵn các nhà ga), và sẽ có một đoàn tàu hoạt động giữa mỗi cặp, sử dụng đường đi ngắn nhất có thể. Tuy nhiên, các đường hầm có những hạn chế của chúng. Mặc dù mỗi đường hầm đều có cùng độ dài (bằng $1$), nhưng chiều rộng của chúng chỉ cho phép một số lượng giới hạn các tuyến đường đi qua.

Các chú lùn muốn tổng độ dài của các tuyến đường tàu hỏa càng dài càng tốt. Bạn có thể tính xem tổng độ dài lớn nhất có thể là bao nhiêu không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $N$, biểu thị số lượng giao lộ trong làng.

Mỗi dòng trong $N - 1$ dòng tiếp theo chứa ba số nguyên $a_i$, $b_i$, $c_i$, biểu thị một đường hầm giữa hai giao lộ $a_i$ và $b_i$. Giá trị $c_i$ là giới hạn trên cho số lượng tuyến đường có thể đi qua đường hầm này.

Kết quả

Trên dòng đầu tiên và duy nhất, hãy in ra một số nguyên duy nhất biểu thị tổng độ dài lớn nhất của các đường đi giữa các cặp nhà ga được chọn.

Nếu không có cách nào để ghép cặp các nhà ga mà vẫn thỏa mãn các ràng buộc, hãy in ra $-1$.

Giới hạn

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, tất cả các giao lộ đều liên thông, và số lượng nhà ga (tức là các ngõ cụt) là số chẵn.

Ví dụ

Dữ liệu vào 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

Kết quả 1

10

Giải thích

Trong ví dụ đầu tiên, việc kết nối các nhà ga tại các giao lộ $5\text{--}9$, $6\text{--}7$, và $8\text{--}10$ cho tổng độ dài các tuyến đường tàu hỏa bằng $4 + 3 + 3 = 10$.

Dữ liệu vào 2

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

Kết quả 2

-1