Farmer John בודק במסירות את הפרות מדי יום. הוא עובר בחלק מתוך $M$ $(1 \le M \le 50,000)$ השבילים, הממוספרים $1,\ldots,M$, ממרעה $1$ עד מרעה $N$ (מסע שתמיד אפשרי במפות השבילים שבנתוני הבדיקה). $N$ $(1 \le N \le 10,000)$ שטחי המרעה בחווה של Farmer John, הממוספרים $1,\ldots,N$, מחוברים כעת בשבילי עפר דו־כיווניים. כל שביל $i$ מחבר את שטחי המרעה $P1_{i}$ ו־$P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$, והמעבר בו דורש $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ יחידות זמן.

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

קלט

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

• שורות $2,\ldots,M+1$: שורה $i+1$ מתארת את שביל $i$ באמצעות שלושה מספרים שלמים המופרדים ברווחים: $P1_{i}$, $P2_{i}$ ו־$T_{i}$.

פלט

• שורה 1: אורך המסלול הקצר ביותר לאחר שיפוץ של לא יותר מ־$K$ קשתות.

דוגמאות

קלט 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

פלט 1

1

הערה

$K$ הוא $1$; שפצו את שביל $3->4$ כך שזמן המעבר בו יהיה $0$ במקום $100$. המסלול הקצר ביותר החדש הוא $1->3->4$, וזמן המעבר הכולל כעת הוא $1$.

מחבר הבעיה: Percy Liang, 2008