1. Bài toán chia cắt địch

Cuối năm 1944, quân Liên Xô phản công vào vùng X, nơi có N thành phố bị phát xít Đức chiếm đóng. Dọc theo các con đường giữa 2 thành phố đều có quân Đức canh giữ. Bộ tham mưu quân sự của Liên Xô mới chỉ đạo phản công tiêu diệt địch, bước đầu thực hiện chia cắt quân địch thành 2 vùng tách biệt để chúng không liên lạc được với nhau, nhưng cần tính toán tiêu diệt như thế nào là lợi nhất mà chỉ cần huy động lực lượng ít nhất để giành thắng lợi. Biết rằng đi tiêu diệt quân Đức thì Liên Xô phải bố trí số quân ít nhất bằng với số quân địch chiếm đóng. Hãy viết chương trình giúp bộ tham mưu quân Liên Xô chỉ cần điều ít nhất lực lượng để giành chiến thắng.

Dữ liệu nhập vào từ file Chiacat.inp

-          Dòng đầu tiên là 2 số nguyên dương N (số thành phố tối đa 100) và M(số con đường nối các cặp 2 thành phố trong vùng X).

-          M dòng tiếp theo, mỗi dòng có 3 số nguyên dương i, j và w thể hiện trên con đường nối thành phố i với thành phố j hiện có w lính Đức.

Kết quả ghi ra file Chiacat.out

-          Dòng đầu là số lượng quân Liên Xô cần điều động

-          Dòng sau, mỗi dòng có 2 số u và v thể hiện con đường (u, v) mà quân Liên Xô cần chiếm lại trong đợt phản công đầu tiên này.