Farmer John רוצה להתקין קו טלפון בחווה. לרוע המזל, חברת הטלפון אינה משתפת פעולה, ולכן עליו לשלם עבור חלק מהכבלים הדרושים לחיבור החווה לרשת הטלפון.

בשטחו פזורים $N$ עמודי טלפון בודדים, $(1 \le N \le 1,000)$, הממוספרים לשם נוחות $1..N$; שום כבל אינו מחבר ביניהם. בסך הכול אפשר לחבר $P$ זוגות עמודים, $(1 \le P \le 10,000)$, באמצעות כבל; שאר הזוגות רחוקים מדי זה מזה.

הכבל ה־$i$ יכול לחבר את שני העמודים השונים $A_i$ ו־$B_i$, ואורכו בשימוש הוא $L_i$ יחידות, $(1 \le L_i \le 1,000,000)$. נתוני הקלט אינם מציינים שום זוג {$A_i,B_i$} יותר מפעם אחת. עמוד $1$ כבר מחובר לרשת הטלפון, ועמוד $N$ נמצא בחווה. יש לחבר את העמודים $1$ ו־$N$ במסלול כבלים; אפשר להשתמש בעמודים האחרים או לא להשתמש בהם.

מתברר שהחברה מוכנה לספק ל־Farmer John $K$ כבלים בחינם, $(0 \le K < N)$. מעבר לכך עליו לשלם מחיר השווה לאורך הכבל הארוך ביותר שעדיין נחוץ לו (כל זוג עמודים מחובר בכבל נפרד), או $0$ אם אין צורך בכבלים נוספים.

מצאו את הסכום המזערי שעל Farmer John לשלם.

קלט

קראו את הקלט מהקלט הסטנדרטי.

• שורה 1: שלושה מספרים שלמים המופרדים ברווחים: $N$, $P$ ו־$K$.

• שורות $2..P+1$: שורה $i+1$ מכילה שלושה מספרים שלמים המופרדים ברווחים: $A_i$, $B_i$ ו־$L_i$.

פלט

כתבו את הפלט לפלט הסטנדרטי.

• שורה 1: מספר שלם אחד, הסכום המזערי ש־Farmer John יכול לשלם. אם אי אפשר לחבר את החווה לחברת הטלפון, הדפיסו $-1$.

דוגמאות

קלט 1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

פלט 1

4

הערה

יש 5 עמודים. אי אפשר לחבר את עמוד $1$ ישירות לעמודים $4$ או $5$. אי אפשר לחבר את עמוד $5$ ישירות לעמודים $1$ או $3$. אפשר לחבר את כל הזוגות האחרים. החברה תספק כבל אחד בחינם.

אם עמוד $1$ מחובר לעמוד $3$, עמוד $3$ לעמוד $2$, ועמוד $2$ לעמוד $5$, Farmer John זקוק לכבלים באורכים $4$, $3$ ו־$9$. החברה תספק את הכבל באורך $9$, ולכן הכבל הארוך ביותר שעדיין נחוץ הוא באורך $4$.

מחבר הבעיה: Paul Christiano, 2007