Bài 5. 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 ≥ 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 tính. 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; thao tác 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; thao tác này mất chi phí ~2 × 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.

Dữ liệu vào

Từ file văn bản BAI5.INP:

• Dòng đầu chứa hai số nguyên dương ~n, m~.
• 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á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.

Kết quả

Ghi ra file văn bản BAI5.OUT gồm một dòng chứa một số là chi phí ít nhất tìm được.

Ví dụ

Ví dụ 1

BAI5.INP
3 3
1 2 1
1 2 2
1 3 1

BAI5.OUT
0

Giải thích: 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

BAI5.INP
3 3
1 2 1
1 2 2
1 2 3

BAI5.OUT
1

Giải thích: Máy 3 không liên thông. Có thể tháo một đầu nối của dây 1 để nối với máy 3, chi phí là 1.

Giới hạn

• ~1 ≤ n ≤ 10^5~, ~n - 1 ≤ m ≤ 2 × 10^5~.
• Với mỗi dây nối, ~1 ≤ u_k, v_k ≤ n~, ~u_k ≠ v_k~ và ~1 ≤ c_k ≤ 10^6~.