Mô tả và yêu cầu

Đua xe Công Thức 1
Thành phố XYZ đang chuẩn bị tổ chức một cuộc đua xe Công Thức 1. Trước khi diễn ra cuộc
đua, chính quyền muốn thiết kế một hệ thống gồm một số camera đặt trên các tuyến đường khác nhau
để phục vụ truyền hình trực tiếp cho người dân. Để tăng tính hấp dẫn của cuộc đua, cần có ít nhất một
camera dọc theo mỗi vòng đua.
Hệ thống đường đua có thể được mô tả bởi một dãy các nút giao thông và các đường nối các
nút giao thông là đường hai chiều. Một vòng đua bao gồm một nút giao thông xuất phát, tiếp theo là
đường đi bao gồm ít nhất 3 tuyến đường và cuối cùng quay trở lại điểm xuất phát. Trong một vòng
đua, mỗi tuyến đường chỉ được đi qua đúng một lần.
Chi phí để đặt camera phụ thuộc vào tuyến đường được chọn, camera được đặt trên các tuyến
đường chứ không phải tại các nút giao thông.
Yêu cầu: Cho n nút giao thông, m tuyến đường nối các nút giao thông và chi phí đặt camera
trên mỗi tuyến đường. Hãy chọn một số tuyến đường để đặt camera sao cho tổng chi phí lắp đặt là thấp
nhất, đồng thời vẫn đảm bảo có ít nhất một camera dọc theo mỗi vòng đua.
Dữ liệu vào từ file ‘RACING.INP’ có nội dung như sau:
- Dòng đầu tiên chứa hai số nguyên n, m (1 ≤ n ≤ 1000; 1 ≤ m ≤ 10000) là số nút giao thông và
số tuyến đường. Các nút giao thông được đánh số từ 1 đến n.
- m dòng tiếp theo mô tả các tuyến đường, mỗi dòng bao gồm 3 số nguyên dương u, v và c, với
ý nghĩa là tuyến đường nối hai nút giao thông u và v có chi phí lắp đặt camera là c (1 ≤ c ≤ 1000).
Dữ liệu luôn đảm bảo hai nút giao thông bất kì đều có thể đi đến được với nhau bằng tuyến
đường trực tiếp hoặc qua các tuyến đường trung gian. Các số cách nhau bởi một dấu cách.
Kết quả ghi vào file ‘RACING.OUT’ một số nguyên duy nhất là tổng chi phí lắp đặt thấp nhất
tìm được.

Ví dụ

RACING.INP             RACING.OUT                                   5                    3
           6 7                    6                                   1                    2                    3

           1 2 5                                                   5                  3                            3
           2 3 3
           1 4 5                                                      4                    5                    6
           4 5 4                                                               4                    4
           5 6 4
           6 3 3
           5 2 3