Một huyện vùng cao có \(N\) xã biệt lập. Để phát triển kinh tế, Ủy ban huyện quyết định trải nhựa một số con đường nối giữa các xã. Hiện tại có \(M\) con đường đất có thể trải nhựa, con đường nối xã \(u\) và xã \(v\) có chi phí trải nhựa là \(c\) tỷ đồng.

Yêu cầu đặt ra là sau khi trải nhựa, từ bất kỳ xã nào cũng có thể đi đến được tất cả các xã khác qua toàn bộ mặt đường nhựa. Bác chủ tịch huyện muốn chọn những con đường sao cho tổng chi phí là nhỏ nhất. Hãy giúp bác tính số tiền cần chuẩn bị nhé!

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5\), \(N-1 \le M \le 2 \times 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\), \(c\) (\(1 \le u, v \le N\), \(1 \le c \le 10^9\)).

Kết quả ra

• In ra tổng chi phí nhỏ nhất. Nếu không thể kết nối tất cả các xã, in ra \(-1\).

Ví dụ

Input

4 5
1 2 10
2 3 8
1 3 5
3 4 7
1 4 3

Output

15

Subtask