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).

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.

Để đề phòng những yếu tố bất định có thể xảy ra, Minh mong bạn giúp cậu thiết kế một kế hoạch B, nội dung cũng là xây các con đường sao cho $N$ khu dân cư liên thông với nhau từng đôi một. Tuy nhiên, yêu cầu kế hoạch B không được hoàn toàn giống với kế hoạch của Minh (tức là hai kế hoạch phải có ít nhất một con đường được xây khác nhau).

Hãy viết chương trình tính chi phí ít nhất để hoàn thành kế hoạch B.

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$.

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 B.

Dữ liệu đảm bảo chắc chắn tồn tại kế hoạch B.

Ví dụ

Input

3 3
1 2 1
2 3 1
1 3 2

Output

3

Ghi chú

Phạm vi dữ liệu

$1 \le N \le 10^5$,

$0 \le M \le 3\times 10^5$,

$1 \le u_i,v_i \le N$,

$0 \le w_i \le 10^9$.