Nước VNOI gồm ~n~ thành phố và đang có kết hoạch liên kết chúng bằng ~m~ con đường cao tốc hai chiều. Các con đường được đánh số từ ~1~ tới ~m~, con đường thứ ~i~ liên kết thành phố ~u_i~ với ~v_i~ và có lợi nhuận là ~w_i~ (các giá trị ~w_i~ phân biệt). Các con đường được thiết kế để tất cả các cặp thành phố đều có thể trực tiếp hoặc gián tiếp đi tới nhau.

Để xây dựng các con đường đó, chính quyền VNOI quyết định giao việc này cho ~k~ nhà thầu. Sau những vòng bỏ phiếu căng thẳng, các nhà thầu này được xếp ở các vị trí từ ~1~ tới ~k~ thể hiện sự ưu tiên trong việc chọn tuyến đường thi công.

Mỗi nhà thầu sẽ được chọn một tập hợp các con đường trong ~m~ đường cao tốc có sẵn trong kế hoạch, sao cho chúng không tạo ra bất kì chu trình nào và con đường không bị nhà thầu nào trước đó chọn. Giả sử, nếu nhà thầu chọn con đường ~\{1 \rightarrow 2; 2 \rightarrow 3; 3 \rightarrow 1; 4 \rightarrow 5\}~ là không thoả mãn, bởi có chu trình ~1 \rightarrow 2 \rightarrow 3 \rightarrow 1~. Lưu ý rằng ở ví dụ trên mũi tên được đánh hướng cho mục đích biểu diễn, còn trên thực tế thì các con đường là hai chiều.

Đầu tiên, nhà thầu thứ ~1~ sẽ được chọn trước, sau đó tới nhà thầu thứ ~2~, ... rồi tới nhà thầu thứ ~k~. Tất nhiên với cách này, một số con đường sẽ không được xây dựng, nhưng ở giai đoạn đầu của dự án thì đây là chuyện bình thường.

Tất nhiên, mỗi nhà thầu đều muốn tối đa hoá lợi ích của mình, vậy nên khi được chọn các con đường, họ sẽ chọn tập con đường mang tới tổng lợi nhuận lớn nhất có thể.

Nhiệm vụ của bạn là tính toán trước cho chính quyền VNOI xem mỗi nhà thầu từ ~1~ tới ~k~ sẽ có lợi nhuận là bao nhiêu khi tất cả đều chọn tập con đường một cách tối ưu.

Input

• Dòng đầu tiên gồm ~3~ số nguyên dương ~n, m, k~ miêu tả số thành phố, số con đường cần xây dựng và số nhà thầu.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên dương ~u_i, v_i, w_i~ miêu tả con đường thứ ~i~ trong kế hoạch, kết nối thành phố ~u_i~ với ~v_i~

Output

• Gồm ~k~ dòng, dòng thứ ~i~ chứa giá trị là tổng lợi nhuận của nhà thầu thứ ~i~ trong cách chia tối ưu.

Subtask

• Trong tất cả các test ~w_i \leq 10^9~
• Có ~20\%~ test tương ứng ~20\%~ số điểm có ~n \le 10^5, m \le 5 \times 10^5; k = 1~.
• Có ~25\%~ test tương ứng ~25\%~ số điểm có ~n \le 10^3, m \le 10^4; k \le 1000~.
• Có ~35\%~ test tương ứng ~35\%~ số điểm có ~n \le 10^3, m \le 5 \times 10^5; k \le 10^4~.
• ~20\%~ số test còn lại ứng với ~20%~ số điểm có ~n \le 10^5, m \le 5 \times 10^5; k \le 10^4~.

Sample