Kéo Cáp Quang Trạm BTS Phú Thọ

Mô tả

Anh Tâm là kỹ thuật viên của Viettel phụ trách mạng cáp quang tại tỉnh Phú Thọ. Tuần tới, anh được giao nhiệm vụ nâng cấp hệ thống truyền dẫn giữa các trạm BTS trên địa bàn tỉnh. Để đảm bảo mọi trạm đều có thể liên lạc được với nhau (trực tiếp hoặc gián tiếp qua các trạm trung gian), anh Tâm cần kéo một mạng lưới cáp quang sao cho từ trạm bất kỳ đều có đường đi tới mọi trạm còn lại. Tất nhiên, càng ít chi phí càng tốt — vì ngân sách đầu tư có hạn.

Mỗi tuyến cáp nối giữa hai trạm có chi phí thi công đã được khảo sát sẵn. Nhiệm vụ của bạn là giúp anh Tâm tính tổng chi phí nhỏ nhất để hoàn thành mạng lưới này.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên n và m: số lượng trạm BTS và số lượng tuyến cáp có thể kéo.
• m dòng tiếp theo, mỗi dòng chứa ba số nguyên u v w: trạm u và trạm v có thể nối bằng tuyến cáp chi phí w.

Đầu ra

• In ra một số nguyên duy nhất: tổng chi phí nhỏ nhất để kéo cáp nối thông toàn bộ các trạm. Nếu không thể nối thông tất cả các trạm, in ra -1.

Ràng buộc

• 1 ≤ n ≤ 10^4
• 0 ≤ m ≤ 5×10^4
• 1 ≤ u, v ≤ n, u ≠ v
• 1 ≤ w ≤ 10^6
• Các trạm được đánh số từ 1 đến n. Giữa hai trạm có thể có nhiều tuyến cáp với chi phí khác nhau.

Ví dụ

Ví dụ 1:

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

Giải thích từng bước:

• Sắp xếp các tuyến theo chi phí tăng dần: (1-3, 1), (2-4, 2), (1-2, 3), (2-3, 4), (3-4, 5).
• Chọn tuyến 1-3 (chi phí 1): trạm 1 và 3 liên thông. Tổng = 1.
• Chọn tuyến 2-4 (chi phí 2): trạm 2 và 4 liên thông. Tổng = 3.
• Chọn tuyến 1-2 (chi phí 3): nối hai nhóm {1,3} và {2,4} lại. Tổng = 6.
• Tuyến 2-3 (chi phí 4) tạo chu trình nên bỏ qua. Tuyến 3-4 (chi phí 5) cũng tạo chu trình nên bỏ qua.
• Đã có 3 tuyến = n-1 = 3, đủ nối 4 trạm. Đáp án: 6.

6

Ví dụ 2:

3 1 1 2 5

Giải thích: Chỉ có một tuyến cáp nối trạm 1 và 2, trạm 3 bị cô lập nên không thể nối thông. Đáp án: -1.

-1