لقد بنى الأقزام للتو قريتهم الجديدة تحت الأرض. حان الوقت الآن لتخطيط شبكة السكك الحديدية التي ستعمل داخلها.

تتكون القرية من $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