Tèo đang thực hiện phân tích quần thể để phân loại các điểm bảo tồn sinh thái hoang dã. Có \(N\) điểm quan trắc bảo tồn và \(M\) tuyến đường tuần tra liên kết tiềm năng kề nhau với độ dài tương ứng.

Tèo cần lựa chọn một số tuyến đường tuần tra để liên kết các điểm quan trắc sao cho toàn bộ các điểm được chia thành đúng \(K\) vùng bảo tồn liên thông độc lập và tổng độ dài các tuyến đường tuần tra được chọn là ngắn nhất.

Định dạng đầu vào

• Dòng đầu chứa ba số nguyên \(N, M, K\) (\(1 \le K \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le N\), \(1 \le w \le 10^9\)) mô tả tuyến đường tuần tra nối \(u\) và \(v\) có độ dài là \(w\).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng độ dài tối thiểu. Nếu không thể chia thành đúng \(K\) vùng liên thông (ví dụ do đồ thị ban đầu có ít hơn \(K\) thành phần liên thông), in ra \(-1\).

Ràng buộc

Ví dụ

Input:

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

Output:

3

(Giải thích ví dụ: Chọn các cạnh (2,3) độ dài 1 và (1,2) độ dài 2. Ta có 2 vùng liên thông độc lập: {1,2,3} và {4} với tổng chi phí 1 + 2 = 3).