Para kurcaci baru saja membangun desa bawah tanah baru mereka. Sekarang saatnya merencanakan jaringan kereta api yang akan beroperasi di dalamnya.

Desa tersebut terdiri dari $N$ persimpangan dan $N - 1$ terowongan yang menghubungkannya. Terowongan-terowongan tersebut telah dibangun sedemikian rupa sehingga memungkinkan untuk mencapai persimpangan mana pun dari persimpangan lainnya. Di setiap persimpangan yang merupakan jalan buntu (artinya hanya terhubung oleh satu terowongan), terdapat sebuah stasiun kereta api.

Tugas Anda adalah menentukan rute untuk kereta api di desa tersebut. Untuk memenuhi persyaratan para kurcaci, semua stasiun harus dipasangkan (untungnya, jumlahnya genap), dan akan ada satu kereta yang beroperasi di antara setiap pasangan, menggunakan jalur terpendek yang mungkin. Namun, terowongan-terowongan tersebut memiliki keterbatasan. Meskipun setiap terowongan memiliki panjang yang sama (sama dengan $1$), lebarnya hanya memungkinkan sejumlah rute terbatas untuk melewatinya.

Para kurcaci menginginkan total panjang rute kereta api sepanjang mungkin. Bisakah Anda menghitung berapa panjang maksimum yang mungkin?

Masukan

Baris pertama masukan berisi satu bilangan bulat $N$, yang menyatakan jumlah persimpangan di desa tersebut.

Masing-masing dari $N - 1$ baris berikutnya berisi tiga bilangan bulat $a_i$, $b_i$, $c_i$, yang menyatakan sebuah terowongan antara persimpangan $a_i$ dan $b_i$. Nilai $c_i$ adalah batas atas jumlah rute yang dapat melewati terowongan ini.

Keluaran

Pada baris pertama dan satu-satunya, cetak satu bilangan bulat yang menyatakan total panjang maksimum jalur antara pasangan stasiun yang dipilih.

Jika tidak ada cara untuk memasangkan stasiun sambil memenuhi batasan yang ada, cetak $-1$.

Batasan

$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, semua persimpangan saling terhubung, dan jumlah stasiun (yaitu jalan buntu) adalah genap.

Contoh

Masukan 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

Keluaran 1

10

Catatan

Pada contoh pertama, menghubungkan stasiun di persimpangan $5\text{--}9$, $6\text{--}7$, dan $8\text{--}10$ memberikan total panjang rute kereta api sama dengan $4 + 3 + 3 = 10$.

Masukan 2

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

Keluaran 2

-1