Thành phố L có tổng cộng $N$ khu dân cư.

Minh là người quy hoạch xây dựng thành phố, cậu dự định xây $M$ con đường trong thành phố, mỗi khi xây một con đường đều phải trả tiền công tương ứng cho các công nhân (tiền công phải trả = độ dài con đường).

Tuy nhiên, kinh phí mà Minh nhận được không đủ để trả tiền công xây $M$ con đường, nên bất đắc dĩ, cậu đành phải thay đổi kế hoạch thành xây một số con đường sao cho $N$ khu dân cư liên thông với nhau từng đôi một.

Minh mong muốn giữ lại càng nhiều kinh phí càng tốt để đầu tư vào các dự án khác, vì vậy hãy viết chương trình giúp cậu tính chi phí thấp nhất cần thiết để hoàn thành kế hoạch.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên dương $N, M$.

Các dòng từ 2 đến $M+1$, mỗi dòng chứa ba số nguyên dương $u, v, w$, biểu thị giữa $u \leftrightarrow v$ tồn tại một con đường có độ dài $w$.

$1 \leq N \leq 10^5$, $0 \leq M \leq 3 \times 10^5$, $1 \leq u_i, v_i \leq N$, $0 \leq w_i \leq 10^9$.

Dữ liệu ra

In ra một dòng chứa một số nguyên, biểu thị chi phí thấp nhất cần thiết để hoàn thành kế hoạch.

Nếu không thể hoàn thành kế hoạch, in ra -1.

Ví dụ

Input

5 6
1 2 2
1 3 7
1 4 6
2 3 1
3 4 3
3 5 2

Output

8