أُعطيت رسمًا بيانيًا موزونًا يحتوي على $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