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≥n-1)\) dây nối giữa các máy tính, dây nối thứ \(k\) \((1≤k≤m)\) nối hai máy tính \(u_k,v_k (u_k≠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×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.

Dữ liệu: Vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng:

• Dòng đầu chứa hai số nguyên dương \(n,m (n≤10^5;n-1≤m≤2×10^5);\)

• Dòng thứ \(k (1≤k≤m)\) trong \(m\) dòng tiếp theo chứa ba số nguyên dương \(u_k,v_k,c_k (c_k≤10^6).\)

Kết quả: Ghi ra thiết bị ra chuẩn (màn hình) một dòng:

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

Sample Input

3 3
1 2 1
1 2 2
1 3 1

Sample Output

0

Sample Input

3 3
1 2 1
1 2 2
1 2 3

Sample Output

1

Ràng buộc

• Subtask 1 (50 điểm):\( c_i=1;\)

• Subtask 2 (25 điểm): \(m,n≤1000;\)

• Subtask 3 (25 điểm): Không có ràng buộc gì thêm.