נתון גרף ממושקל בעל $n$ קודקודים. עליכם למצוא תת־גרף קשיר בעל משקל כולל מינימלי, המכיל את כל הקודקודים שמספריהם מ־$1$ עד $n-k$, כולל שני הקצוות.

כדי להקל על פתרון הבעיה ועל יצירת הבדיקות, כל הבדיקות מלבד הדוגמאות נוצרות באמצעות האלגוריתם הבא:

• חבר השופטים בוחר את המספרים השלמים $n$, $m$ ו־$k$.
• כל $\frac{n\cdot(n-1)}{2}$ הקשתות האפשריות נבחנות בסדר אקראי.
• הקשת הנבחנת מתווספת לגרף אם לאחר הוספתה עדיין אפשר להוסיף אפס או יותר מהקשתות הבאות ולקבל גרף קשיר המכיל בסך הכול לכל היותר $m$ קשתות.
• לכל קשת, משקלה הוא מספר שלם שנבחר באקראי בהתפלגות אחידה מהקטע $[50,100]$, באופן בלתי תלוי בקשתות האחרות.

קלט

השורה הראשונה מכילה שלושה מספרים שלמים $n$ ($5 \le n \le 100$), $m$ ($2\cdot n \le m \le 10\cdot n$) ו־$k$ ($0 \le k \le 30$). כל אחת מ־$m$ השורות הבאות מכילה שלושה מספרים שלמים $a_i$, $b_i$ ו־$w_i$ ($1 \le a_i < b_i \le n$, $50 \le w_i \le 100$), המציינים שהקודקודים $a_i$ ו־$b_i$ מחוברים בקשת שמשקלה $w_i$.

מובטח שאין בגרף לולאות עצמיות או קשתות מקבילות. בנוסף, מובטח שבכל הבדיקות מלבד הדוגמאות הגרף נוצר באמצעות האלגוריתם המתואר לעיל.

פלט

בשורה הראשונה הדפיסו מספר שלם אחד $c$, מספר הקשתות בתת־הגרף שנבחר. ב־$c$ השורות הבאות הדפיסו את הקשתות שנבחרו: מספרי הקודקודים המחוברים בכל קשת. אם יש כמה תשובות אפשריות, הדפיסו אחת מהן.

דוגמאות

קלט 1

5 10 3
1 2 50
1 3 51
1 4 52
1 5 53
2 3 54
2 4 55
2 5 56
3 4 57
3 5 58
4 5 59

פלט 1

1
1 2

קלט 2

5 10 2
1 2 100
1 3 100
1 4 57
1 5 56
2 3 100
2 4 54
2 5 53
3 4 52
3 5 51
4 5 50

פלט 2

3
5 2
5 3
1 5