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 \geq n-1\)) dây nối giữa các máy tính, dây nối thứ \(k\) (\(1 \leq k \leq m\)) nối hai máy tính \(u_k\), \(v_k\) (\(u_k \neq v_k\)) và giúp truyền tin theo cả hai chiều giữa hai máy tính. 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.

Input

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

Output

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

Example

3 3
1 2 1
1 2 2
1 3 1

0

3 3
1 2 1
1 2 2
1 2 3

1

Ràng buộc

• 50% số điểm của bài ứng với các test có \(c_k = 1, 1 \leq k \leq m\).
• 25% số điểm của bài ứng với các test có \(m, n \leq 10^3\).
• 25% số điểm của bài ứng với các test không có ràng buộc gì thêm.