Công ty của Alice 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 \neq 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, Alice 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, cụ thể, cô 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: Hãy giúp Alice 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 \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~).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số là chi phí ít nhất tìm được.

Sample Input 1

3 3
1 2 1
1 2 2
1 3 1

Sample Output 1

0

Sample Input 2

3 3
1 2 1
1 2 2
1 2 3

Sample Output 2

1

Subtasks

• Subtask 1 (40 điểm): ~c_i = 1~;
• Subtask 2 (30 điểm): ~m, n \le 1000~;
• Subtask 3 (30 điểm): Không có ràng buộc gì thêm.