Trung tâm tin học của Nam có ~n~ máy tính, các máy tính được đánh số từ ~1~ đến ~n~. Hiện tại đang có ~m~ (~m \ge n - 1~) dây nối giữa các máy tính, dây nối thứ ~k~ (~1 \le k \le m~) nối hai máy tính ~u_k~, ~v_k~ (~u_k \ne v_k~) và giúp truyền tin theo cả hai chiều giữa hai máy, có thể có nhiều dây nối giữa hai máy tính. Hiện tại, ~n~ máy tính có thể không liên thông với nhau, Nam có thể tháo dây nối để đầu nối lại với mong muốn làm cho ~n~ máy tính liên thông, Nam có thể thực hiện:

• Tháo một đầu nối của dây thứ ~k~ để đầu nối sang máy tính khác, hành động này mất chi phí ~c_k~;
• Tháo cả hai đầu nối của dây thứ ~k~ để đầu nối sang hai máy tính khác, hành động này mất chi phí ~2 \times c_k~.

Yêu cầu: Tính chi phí ít nhất cần thực hiện để liên thông được ~n~ máy tính.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương ~n~, ~m~ (~n \le 10^5~; ~n - 1 \le m \le 2 \times 10^5~).
• Dòng thứ ~k~ (~1 \le k \le m~) trong ~m~ dòng tiếp theo chứa ba số nguyên dương ~u_k~, ~v_k~, ~c_k~ (~c_k \le 10^6~).

Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi dấu cách.

Kết quả

• Gồm một dòng chứa một số là chi phí ít nhất tìm được.

Ví dụ

Đầu vào:

3 3
1 2 1
1 2 2
1 3 1

Đầu ra:

0

Giải thích: Các máy đã liên thông nên không cần nối dây. Chi phí là ~0~.

Đầu vào:

3 3
1 2 1
1 2 2
1 2 3

Đầu ra:

1

Giải thích: Máy ~3~ không liên thông, tháo một đầu nối của dây ~1~ (~u_1 = 1~, ~v_1 = 2~, ~c_1 = 1~) nối với máy ~3~. Chi phí là ~1~.

Giới hạn

• ~1 \le n \le 10^5~
• ~n - 1 \le m \le 2 \times 10^5~
• ~1 \le u_k, v_k \le n~, ~u_k \ne v_k~
• ~1 \le c_k \le 10^6~

Điểm của một subtask chỉ được tính khi tất cả các test thuộc subtask đó đều đúng.