Mô tả bài toán

Farmer John (FJ) dự định kéo một đường dây điện thoại đến trang trại của mình, nhưng công ty viễn thông không có ý định cung cấp dịch vụ miễn phí cho ông. Vì vậy, FJ phải trả một khoản phí nhất định cho công ty viễn thông để kéo đường dây này. Có N (1 ≤ N ≤ 1.000) cột điện thoại đánh số từ 1 đến N xung quanh trang trại của FJ.

Hiện tại, không có đường dây điện thoại nào kết nối giữa các cột điện thoại. Có tổng cộng P (1 ≤ P ≤ 10.000) cặp cột điện thoại có thể kết nối với nhau, còn lại thì không kết nối được với nhau. Hai điểm cuối của cặp thứ i là Aᵢ và Bᵢ, và khoảng cách giữa chúng là Lᵢ (1 ≤ Lᵢ ≤ 1.000.000). Dữ liệu đảm bảo rằng mỗi cặp {Aᵢ, Bᵢ} xuất hiện một lần duy nhất.

Cột điện thoại đánh số 1 đã được kết nối với mạng viễn thông quốc gia, và tất cả các cột điện thoại khác trong trang trại đều phải kết nối với cột điện thoại đánh số 1. Nói cách khác, nhiệm vụ của FJ là đảm bảo một mạng lưới liên thông gồm N cột điện thoại, trong đó cột số 1 là trung tâm. Các cột điện thoại còn lại không cần phải trực tiếp kết nối với cột số 1 mà có thể thông qua các cột khác.

Sau khi đàm phán, công ty viễn thông đồng ý kết nối miễn phí tối đa K (0 ≤ K < N) cặp cột điện thoại. Đối với các đường dây còn lại, FJ phải trả chi phí bằng tổng chiều dài của các đường dây đó (mỗi đường dây chỉ kết nối một cặp cột điện thoại). Nếu số lượng cột điện thoại được kết nối không vượt quá K cặp, thì tổng chi phí của FJ là 0.

Yêu cầu: Tính tổng chi phí tối thiểu mà FJ phải chi cho dự án này. Nếu không thể hoàn thành nhiệm vụ, xuất -1.

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

• Dòng 1: Ba số nguyên cách nhau bởi dấu cách: N, P, K.
• Các dòng từ 2 đến P + 1: Mỗi dòng chứa ba số nguyên cách nhau bởi dấu cách: Aᵢ, Bᵢ, Lᵢ.

Định dạng đầu ra

• Dòng 1: Xuất ra một số nguyên, đó là chi phí tối thiểu mà FJ phải chi cho dự án này. Nếu không thể hoàn thành nhiệm vụ, xuất -1.

Ví dụ:

Input:

5 7 1
1 2 5
3 1 4
2 4 8
3 5 9
5 2 9
3 4 7
4 5 6

Output:

4

Giải thích

Nhập mô tả:

Tổng cộng có 5 cột điện thoại bị bỏ hoang. Cột điện thoại 1 không thể kết nối trực tiếp với cột điện thoại 4 và 5. Cột điện thoại 5 không thể kết nối trực tiếp với cột điện thoại 1 và 3. Dây điện thoại có thể được chạy giữa tất cả các cột điện thoại khác.

• Công ty có thể kết nối miễn phí một cặp cột điện thoại với FJ.

Mô tả đầu ra:

FJ chọn phương án nối sau: 1 -> 3 -> 2 -> 3 -> 2 -> 5, cần có ba cặp cột điện thoại này. Chiều dài của các đường dây điện thoại lần lượt là 4, 3 và 9. FJ yêu cầu công ty viễn thông cung cấp đường dây điện thoại dài 9, vì vậy độ dài tối đa của sợi dây điện thoại anh ta cần mua là 4.