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 \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, 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 máy tính.

Dữ liệu vào

• Dòng đầu cha 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 dòng tiếp theo chứa ba số nguyên dương \(u_{k}, v_{k}, c_{k}\) \((c_{k} \leq 10^{6})\).

Dữ liệu ra

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

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(c_{i} = 1\).
• Subtask \(2\) (\(25\%\) số điểm): \(m, n \leq 1000\).
• Subtask \(3\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Input 1

3 3
1 2 1
1 2 2
1 3 1

Output 1

0

Input 2

3 3
1 2 1
1 2 2
1 2 3

Output 2

1