กำหนดกราฟถ่วงน้ำหนักที่มีจุดยอด $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