Mạng phủ tối đa

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

Trong một bài toán độ tin cậy, trọng số cạnh là điểm chất lượng và mục tiêu là chọn n-1 cạnh tạo cây khung với tổng điểm lớn nhất.

Yêu cầu

Tính tổng trọng số của maximum spanning tree; nếu không thể 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 tổng lớn nhất hoặc "IMPOSSIBLE".

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 3*10^5
• -10^9 <= 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

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

Output

17

Giải thích. Sắp cạnh giảm dần và áp dụng Kruskal cho cây khung có tổng trọng số lớn nhất.

Ví dụ 2

Input

3 1
1 2 10

Output

IMPOSSIBLE

Giải thích. Sắp cạnh giảm dần và áp dụng Kruskal cho cây khung có tổng trọng số lớn nhất.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.