Bạn là một kỹ sư phần mềm làm việc cho Sở Giao thông Vận tải của một thành phố thông minh. Thành phố này có N địa điểm quan trọng và M tuyến đường hai chiều kết nối giữa các địa điểm đó. Mỗi tuyến đường thứ i nối liền địa điểm a_i và b_i, đồng thời người dân sẽ mất một khoảng thời gian là c_i phút để di chuyển qua nó.
Hệ thống đường xá này đảm bảo rằng người dân luôn có cách để đi từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác (đồ thị liên thông).
Hiện tại, ngân sách bảo trì đường bộ của thành phố đang bị thâm hụt nghiêm trọng. Thị trưởng quyết định phải cắt giảm chi phí bằng cách đóng cửa bớt một số tuyến đường.
Qua khảo sát, Sở Giao thông nhận thấy một thói quen của người dân thành phố thông minh: Họ luôn luôn sử dụng ứng dụng bản đồ (như Google Maps) để tìm và đi theo tuyến đường có thời gian ngắn nhất (Shortest Path) giữa điểm xuất phát và điểm đến. Nếu có nhiều lộ trình cùng đạt thời gian ngắn nhất, họ có thể đi bất kỳ lộ trình nào trong số đó.
Từ đó, Thị trưởng đưa ra một quyết định táo bạo: "Nếu một tuyến đường không bao giờ nằm trên bất kỳ một lộ trình ngắn nhất nào giữa bất kỳ cặp 2 địa điểm nào trong thành phố, tuyến đường đó là vô dụng và không ai thèm đi cả. Chúng ta sẽ đóng cửa những tuyến đường này!".
Nhiệm vụ của bạn là viết một chương trình phân tích bản đồ thành phố và đếm xem: Có bao nhiêu tuyến đường "bị lãng quên" sẽ bị đóng cửa theo chỉ thị của Thị trưởng?
