Vương quốc Tân Á có \(N\) ngôi làng và \(M\) con đường nối các làng. Một số đường được lát đá, các đường còn lại được làm bằng bê tông. Việc duy trì các con đường miễn phí tốn rất nhiều tiền, nên vương quốc không thể giữ tất cả các con đường miễn phí và cần một kế hoạch mới.

Nhà vua quyết định giữ số đường miễn phí ít nhất có thể, nhưng giữa mỗi hai ngôi làng phân biệt phải có đúng một đường đi chỉ sử dụng các con đường miễn phí. Mặc dù đường bê tông phù hợp với giao thông hiện đại hơn, nhà vua thấy đi trên đường lát đá rất thú vị. Vì vậy, ông yêu cầu giữ miễn phí đúng \(K\) con đường lát đá.

Hình dưới minh họa một mạng đường và một kế hoạch hợp lệ khi \(K=2\). Đường liền là đường bê tông, đường nét đứt là đường lát đá; hình bên phải chỉ vẽ các đường được giữ miễn phí.

Hãy xác định có kế hoạch nào thỏa mãn yêu cầu của nhà vua hay không. Nếu có, hãy đưa ra một kế hoạch hợp lệ.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(N,M,K\), lần lượt là số ngôi làng, số con đường và số đường lát đá cần được giữ miễn phí.

\(M\) dòng tiếp theo mô tả các con đường được đánh số từ \(1\) đến \(M\). Dòng thứ \(i\) trong số này chứa ba số nguyên \(u_i,v_i,c_i\): con đường thứ \(i\) nối hai làng \(u_i,v_i\); \(c_i=0\) nếu đó là đường lát đá và \(c_i=1\) nếu đó là đường bê tông.

Các ngôi làng được đánh số từ \(1\) đến \(N\). Không có quá một con đường nối cùng một cặp làng. Các con đường có thể đi theo cả hai chiều.

Dữ liệu ra

Nếu không có kế hoạch thỏa mãn, in no solution trên dòng đầu tiên.

Nếu có, liệt kê các con đường được giữ miễn phí, mỗi đường trên một dòng gồm ba số \(u_i,v_i,c_i\) mô tả đường đó như trong dữ liệu vào. Các con đường có thể được liệt kê theo thứ tự bất kỳ. Nếu có nhiều kế hoạch hợp lệ, bạn có thể in bất kỳ kế hoạch nào. Một kế hoạch hợp lệ gồm \(N-1\) con đường, nối tất cả các làng, không tạo chu trình và có đúng \(K\) đường lát đá.

Ràng buộc

Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(128\) MB. Một bộ dữ liệu chỉ được tính điểm khi kết quả hoàn toàn đúng.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1

3 2 0
4 3 0
1 2 1
5 3 1

Nguồn

Olympic Tin học châu Á – Thái Bình Dương 2008, bài Roads.