Mạng máy tính

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.

Input

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.

Ràng buộc:

• \(50\%\) số điểm của bài ứng với các test có \(c_k = 1\), \(1 \le k \le m\);

• \(25\%\) số điểm của bài ứng với các test có \(m, n \le 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.

Output

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

Example 1

Input:

3 3
1 2 1
1 2 2
1 3 1

Output:

0

Example 2

Input:

3 3
1 2 1
1 2 2
1 2 3

Output:

1

Note

Ví dụ 1: Các máy đã liên thông nên không cần nối dây. Chi phí là \(0\).

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