เหล่าคนแคระเพิ่งสร้างหมู่บ้านใต้ดินแห่งใหม่เสร็จ ตอนนี้ได้เวลาวางแผนเครือข่ายทางรถไฟที่จะเดินรถภายในหมู่บ้านแล้ว

หมู่บ้านประกอบด้วยทางแยก $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