An được giao nhiệm vụ lên kế hoạch khôi phục giao thông giữa \(N\) thành phố (được đánh số từ \(1\) đến \(N\)). Hiện tại giữa một số cặp thành phố có các tuyến đường đất tiềm năng nối hai chiều kề nhau với chi phí rải nhựa là \(w\).

Hãy tìm tổng chi phí tối thiểu để khôi phục một số tuyến đường sao cho tất cả \(N\) thành phố liên thông với nhau (tức là luôn có đường đi giữa hai thành phố bất kỳ).

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

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(0 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le N\), \(1 \le w \le 10^9\)) mô tả tuyến đường giữa \(u\) và \(v\) có chi phí khôi phục là \(w\).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí tối thiểu. Nếu không thể kết nối tất cả các thành phố, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

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

Output:

7