בהשראת פארק המים החדש ב-Machu Picchu בפרו, Farmer John בונה אחד לפרות. האטרקציה העיקרית תהיה מגלשת מים ענקית בעיצוב מיוחד.

היא מורכבת מ-$E$ מגלשות קטנות ($1 \le E \le 150,000$) בין $V$ בריכות ($2 \le V \le 50,000$), המסומנות $1..V$. עוברים רק בכיוון הנכון ולא אחורה. הפרות מתחילות ב-1 ומגיעות לסופית $V$. לכל בריכה חוץ מ-1 לפחות מגלשה נכנסת אחת; חוץ מ-$V$, לפחות אחרת יוצאת.

מכל בריכה אפשר להגיע לסוף $V$. אי אפשר לצאת מבריכה ולחזור אליה אחרי כמה מגלשות.

מגלשה $i$ מ-$P_{i}$ ל-$Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$), עם הנאה $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$). ההנאה הכוללת של Bessie היא סכום הערכים שעברה.

לאחר תור ארוך היא רוצה מקסימום הנאה. לרוב בוחרת יציאות בקפידה, אך כפרה מאבדת שליטה לכל היותר $K$ פעמים ($1 \le K \le 10$) ועוקבת אחרי יציאה אקראית, אפילו ב-1.

כמה הנאה מובטחת אם תבחר למקסם את המקרה הגרוע?

לדוגמה: 3 בריכות, מספרים בסוגריים מרובעים, 4 מגלשות ו-$K$ שווה 1; הנאה מחוץ לסוגריים:

          [1]
         /   \
   5 -> /     \ <- 9
       /       \
     [2]---3---[3]
        \__5__/

תמיד מ-1 ל-3. בחופשיות הייתה בוחרת 1 ל-2 ואז מגלשה עם הנאה 5 ל-3: $5+5=10$. איבוד שליטה ב-1 עשוי להוביל ישר ל-3 עם 9, וב-2 רק $5+3 = 8$.

היא בוחרת $1\to3$ עבור 9. אם תאבד שליטה ב-1 ותיקח $1\to2$, לא תאבד ב-2 ותגיע ל-10. לכן מבטיחה לפחות 9.

קלט

• שורה $1$: שלמים $V$, $E$, $K$ מופרדים ברווחים.
• שורות $2..E + 1$: שורה $i+1$ מכילה שלמים $P_{i}$, $Q_{i}$, $F_{i}$ מופרדים ברווחים.

פלט

• שורה $1$: שלם אחד, ההנאה המינימלית המובטחת ל-Bessie.

דוגמאות

קלט 1

3 4 1
2 3 5
1 2 5
1 3 9
2 3 3

פלט 1

9

מחבר הבעיה: John Pardon, 2010