Phần chi phí có thể loại bỏ

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

Một mạng hiện có tất cả m tuyến đang được duy trì, tổng chi phí là tổng trọng số. Ta muốn chỉ giữ lại một hệ thống con liên thông có tổng chi phí nhỏ nhất.

Yêu cầu

Tính tổng chi phí có thể tiết kiệm được = tổng chi phí ban đầu - chi phí MST. Nếu mạng ban đầu không liên thông, in -1.

Input

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

Output

In số tiền tiết kiệm hoặc -1.

Ràng buộc

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

Output

14

Giải thích. Khoản tiết kiệm bằng tổng chi phí tất cả cạnh trừ chi phí MST.

Ví dụ 2

Input

3 1
1 2 5

Output

-1

Giải thích. Khoản tiết kiệm bằng tổng chi phí tất cả cạnh trừ chi phí MST.

Thông tin bài tập

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