Hệ thống giao thông công cộng tại thành phố X có ~N~ giao lộ, hai giao lộ bất kỳ có thể được kết nối bởi:

• Một đường xe hai chiều đơn làn: tốc độ tối đa thấp hơn, phí bảo trì thấp hơn; hoặc
• Một đường xe hai chiều đa làn: tốc độ tối đa cao hơn, phí bảo trì cao hơn.

Vì phí bảo trì hệ thống rất lớn, thành phố quyết định sẽ cắt bỏ bớt một số đường xe sao cho:

• Bất kỳ hai giao lộ nào đều có thể đến được với nhau bằng các đường xe đơn làn hoặc đa làn, nhằm đảm bảo tính liên thông của hệ thống.
• Có chính xác ~K~ đường xe đa làn được giữ lại, nhằm đảm bảo tính lưu thông của hệ thống.

Bạn hãy giúp thành phố xác định một hệ thống giao thông thoả mãn các yêu cầu trên. Đương nhiên, một hệ thống như thế sẽ có chính xác ~K~ đường xe đa làn và ~N - K - 1~ đường xe đơn làn.

Yêu cầu: Hãy tìm một hệ thống giao thông thoả mãn các điều kiện trên hoặc thông báo không tồn tại.

Input

• Dòng đầu tiên chứa ba số nguyên không âm ~N, M, K~ (~2 \le N \le 10^5, 1 \le M \le 2 \cdot 10^5, 0 \le K \le N - 1~), biểu thị số giao lộ, số đường xe và số đường xe đa làn cần giữ lại ở hệ thống tối thiểu.
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm ~u_i, v_i, c_i~ mô tả một đường xe hai chiều (~u_i, v_i~) thuộc loại đường đa làn nếu ~c_i = 0~, hoặc đơn làn nếu ~c_i = 1~ (~1 \le u_i, v_i \le N, 0 \le c_i \le 1~). Dữ liệu đảm bảo mỗi cạnh vô hướng (~u_i, v_i~) chỉ xuất hiện tối đa 1 lần.

Output

• Nếu không có phương án nào hợp lệ, in ra NO.
• Ngược lại, in ra đúng ~N~ dòng. Dòng đầu tiên in ra YES, mỗi dòng trong ~N - 1~ dòng tiếp theo chứa ba số nguyên (~u'_j, v'_j, c'_j~) miêu tả các đường xe được chọn ở hệ thống tối thiểu. Dữ liệu in ra phải đảm bảo ~\sum c'_j = N - K - 1~, và cạnh (~u'_j, v'_j, c'_j~) là một cạnh của đồ thị ban đầu.