Cho đồ thị vô hướng liên thông có trọng số gồm \(N\) đỉnh và \(M\) cạnh. Bạn hãy tìm tổng trọng số của cây khung nhỏ nhất (Minimum Spanning Tree - MST) của đồ thị bằng thuật toán Kruskal kết hợp cấu trúc dữ liệu các tập hợp không giao nhau (Disjoint Set Union - DSU).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(1 \le M \le 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) biểu thị một cạnh vô hướng nối đỉnh \(u\) và đỉnh \(v\) có trọng số \(w\) (\(1 \le u, v \le N\), \(1 \le w \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng trọng số các cạnh của cây khung nhỏ nhất.

Ví dụ

Input:

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

Output:

7

Ràng buộc

• 30% số điểm ứng với \(N, M \le 1000\).
• 70% số điểm còn lại không có ràng buộc gì thêm.