Đề bài:

Đối phương có n địa điểm phòng thủ chiến lược, các địa điểm được đánh số từ 1 tới n (2 ≤ n ≤ 150, 0 ≤ m ≤ ). Giữa các địa điểm này có m đường nối. Kế hoạch tấn công được vạch ra theo phương án bắt đầu bằng việc ném bom phá huỷ các đường giao thông sao cho tồn tại ít nhất một cặp 2 vị trí chiến lược không còn đường liên hệ với nhau, trong trường hợp đó sức mạnh phòng thủ của địch sẽ bị giảm sút một cách đáng kể. Các đường nối giữa các vị trí đi qua các địa hình khác nhau và có độ kiên cố khác nhau, vì vậy chi phí để ném bom phá huỷ hoàn toàn khả năng lưu thông mỗi đường sẽ khác nhau.

Yêu cầu: Cho n, m , các cặp (i, j) cho biết có đường nối giữa 2 vị trí i và j, chi phí v (1 ≤ v ≤ 1 000) để phá huỷ đường này. Hãy xác định chi phí tối thiểu cần thiết để đạt được mục tiêu đề ra.

Với trường hợp nêu ở hình trên, chi phí tối thiểu sẽ là 30.

Dữ liệu: Vào từ file văn bản BOMBING.INP

• Dòng đầu tiên chứa số nguyên n,

• Dòng thứ 2 chứa số nguyên m,

• m dòng sau: mỗi dòng chứa 3 số nguyên i j v.

Kết quả: Đưa ra file văn bản BOMBING.OUT một số nguyên duy nhất là tổng chi phí tối thiểu cần dùng.

Ví dụ: