Mạng công ty

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\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, 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$.

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

• 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$).

Dữ liệu ra

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

Ràng buộc

• $n\le {10}^5$
• $n-1\le m\le 2\times {10}^5$
• $c_k\le {10}^6$
• Subtask 1 (50 điểm): $c_i=1$
• Subtask 2 (25 điểm): $m,n\le 1000$
• Subtask 3 (25 điểm): Không có ràng buộc gì thêm.

Ví dụ