הגמדים סיימו זה עתה לבנות את הכפר התת-קרקעי החדש שלהם. כעת הגיע הזמן לתכנן את רשת מסילות הרכבת שתפעל בתוכו.

הכפר מורכב מ-$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