Tối thiểu hóa chi phí phục hồi mạng

Bối cảnh và bài toán

Có n trạm và m tuyến cáp có thể phục hồi. Mỗi tuyến có chi phí riêng. Cần chọn một số tuyến để mọi trạm kết nối với nhau với tổng chi phí nhỏ nhất.

Yêu cầu

Tính chi phí nhỏ nhất; nếu không thể kết nối toàn bộ, in IMPOSSIBLE.

Input

Dòng đầu n, m; tiếp theo m cạnh vô hướng u, v, w.

Output

In chi phí MST hoặc "IMPOSSIBLE".

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 3*10^5
• 1 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

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

Output

14

Giải thích. Kruskal chỉ thêm cạnh nối hai component khác nhau; tổng cuối là chi phí cây khung nhỏ nhất.

Ví dụ 2

Input

3 1
1 2 5

Output

IMPOSSIBLE

Giải thích. Kruskal chỉ thêm cạnh nối hai component khác nhau; tổng cuối là chi phí cây khung nhỏ nhất.

Gợi ý

Hãy bắt đầu bằng cách phân loại graph, mục tiêu truy vấn và constraints; sau đó đối chiếu với Decision Map của buổi học trước khi viết code.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Road Reparation. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.