Ông JOI, một đại gia sở hữu toàn bộ đường sắt của quốc gia IOI, đã qua đời. Các tuyến đường sắt sẽ được chia thừa kế theo di chúc của ông.

Quốc gia IOI có \(N\) thành phố và \(M\) tuyến đường sắt. Các thành phố được đánh số từ \(1\) đến \(N\), các tuyến đường sắt được đánh số từ \(1\) đến \(M\). Tuyến \(i\) nối hai chiều thành phố \(A_i\) và \(B_i\), đồng thời mang lại doanh thu \(C_i\) yên mỗi năm. Vì lượng hành khách và giá vé khác nhau, các giá trị \(C_1,\ldots,C_M\) đôi một khác nhau. Có thể có nhiều tuyến nối cùng một cặp thành phố.

Di chúc quy định cách chia thừa kế như sau:

• Các tuyến đường sắt được chia cho \(K\) người con, đánh số từ \(1\) đến \(K\) theo thứ tự từ lớn tuổi đến nhỏ tuổi.
• Mỗi người con thừa kế một số tuyến trong \(M\) tuyến, có thể là không tuyến nào.
• Đầu tiên, người con \(1\) chọn một số tuyến làm phần thừa kế. Sau đó người con \(2\) chọn trong các tuyến còn lại, rồi tiếp tục như vậy đến người con \(K\).
• Không ai được chọn một tuyến đã có người lớn tuổi hơn chọn.
• Khi chọn phần của mình, mỗi người phải bảo đảm các tuyến mình nhận không chứa chu trình. Nói cách khác, nếu có thể dùng mỗi tuyến trong một tập các tuyến phân biệt đúng một lần để xuất phát và quay lại cùng một thành phố, thì không người con nào được thừa kế toàn bộ tập đó.
• Các tuyến không ai nhận sẽ được hiến tặng cho quốc gia IOI.

Giống cha mình, mỗi người con đều tham lam và chọn phần thừa kế sao cho tổng doanh thu hằng năm lớn nhất có thể. Có thể chứng minh rằng đối với mỗi người, cách chọn đạt tổng doanh thu lớn nhất là duy nhất.

Yêu cầu

Hãy xác định người thừa kế của từng tuyến đường sắt.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(N,M,K\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,C_i\).

Dữ liệu ra

In ra \(M\) dòng. Dòng thứ \(i\) chứa số hiệu người con thừa kế tuyến \(i\); nếu tuyến đó được hiến tặng cho quốc gia IOI, in ra 0.

Ràng buộc

• \(2 \le N \le 1\,000\).
• \(1 \le M \le 300\,000\).
• \(1 \le K \le 10\,000\).
• \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\) với mọi \(1 \le i \le M\).
• \(1 \le C_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le M\).
• \(C_i \ne C_j\) với mọi \(1 \le i<j \le M\).

Phân nhóm

• Nhóm 1 (15 điểm): \(K \le 10\)
• Nhóm 2 (85 điểm): Không có ràng buộc bổ sung

Ví dụ

3 5 2
1 2 3
1 2 1
2 3 4
2 3 6
1 3 2

1
0
2
1
2

3 6 5
1 2 1
1 2 2
2 3 3
2 3 4
3 1 5
3 1 6

4
3
2
1
2
1