Cho một đồ thị có trọng số gồm $n$ đỉnh. Nhiệm vụ của bạn là tìm một đồ thị con liên thông có tổng trọng số nhỏ nhất và chứa tất cả các đỉnh có số hiệu từ $1$ đến $n-k$, kể cả hai đầu.

Để bài toán dễ giải hơn và các bộ kiểm thử dễ sinh hơn, mọi bộ kiểm thử trừ các ví dụ đều được sinh bằng thuật toán sau:

• Ban giám khảo chọn các số nguyên $n$, $m$ và $k$.
• Xét tất cả $\frac{n\cdot(n-1)}{2}$ cạnh có thể có theo thứ tự ngẫu nhiên.
• Cạnh đang xét được thêm vào đồ thị nếu sau khi thêm cạnh đó, vẫn có thể thêm không hoặc nhiều cạnh trong các cạnh tiếp theo để thu được một đồ thị liên thông có tổng cộng không quá $m$ cạnh.
• Với mỗi cạnh, trọng số là một số nguyên được chọn ngẫu nhiên đều từ đoạn $[50,100]$, độc lập với các cạnh khác.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $n$ ($5 \le n \le 100$), $m$ ($2\cdot n \le m \le 10\cdot n$) và $k$ ($0 \le k \le 30$). Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $a_i$, $b_i$ và $w_i$ ($1 \le a_i < b_i \le n$, $50 \le w_i \le 100$), cho biết các đỉnh $a_i$ và $b_i$ được nối bởi một cạnh có trọng số $w_i$.

Đảm bảo đồ thị không có khuyên và không có cạnh bội. Ngoài ra, đảm bảo trong mọi bộ kiểm thử trừ các ví dụ, đồ thị được sinh bằng thuật toán mô tả ở trên.

Dữ liệu ra

Ở dòng đầu tiên, in một số nguyên $c$, là số cạnh của đồ thị con được chọn. Trong $c$ dòng tiếp theo, in các cạnh được chọn: số hiệu của hai đỉnh được nối bởi mỗi cạnh. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

1
1 2

Dữ liệu vào 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

Dữ liệu ra 2

3
5 2
5 3
1 5