Một quốc gia có thành phố và một danh sách các tuyến đường sắt tiềm năng có thể được xây dựng. Có tuyến đường tiềm năng, tuyến thứ nối thành phố và với chi phí xây dựng là . Chính phủ muốn xây dựng một mạng lưới đường sắt để đảm bảo có thể đi lại giữa hai thành phố bất kỳ, đồng thời tổng chi phí xây dựng phải là nhỏ nhất.
Hãy tính tổng chi phí tối thiểu đó.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên .
dòng tiếp theo, mỗi dòng chứa ba số nguyên mô tả một tuyến đường tiềm năng.
Kết quả: Một số nguyên duy nhất là tổng chi phí nhỏ nhất. Nếu không thể kết nối tất cả các thành phố, in ra IMPOSSIBLE.
Ví dụ:
Dữ liệu:
5 7
1 2 3
1 3 5
2 3 2
2 4 8
3 4 4
3 5 6
4 5 1
Kết quả:
10
Giải thích: Chọn các cạnh (2, 3) chi phí 2, (4, 5) chi phí 1, (1, 2) chi phí 3, (3, 4) chi phí 4. Tổng chi phí là .
