Thành phố ACM quyết định tổ chức một cuộc đua xe hậu Valentine. Thành phố gồm n nút giao thông và không có con đường nào nối 2 nút giao thông bất kỳ. Vì vậy ban tổ chức (BTC) muốn xây dựng các đường đua nối các nút giao thông lại với nhau tạo thành các vòng đua. Sau khi tham khảo giá cả từ công ty MCA, BTC đưa ra một danh sách gồm m con đường một chiều nối giữa 2 nút giao thông có thể xây dựng và giá của chúng. Vì muốn xây dựng thật nhiều vòng đua (như vậy sẽ có nhiều cuộc đua diễn ra song song), BTC muốn tất cả các nút giao thông đều được sử dụng trong cuộc đua và mỗi nút giao thông chỉ thuộc đúng một vòng đua (nghĩa là từ một nút giao thông chỉ có thể di chuyển tới các nút giao thông khác thuộc cùng một vòng đua). Chi phí xây dựng cuộc đua là tổng chi phí xây dựng các vòng đua, trong đó chi phí xây dựng một vòng đua là tổng chi phí xây dựng các đường đua thuộc vòng đua đó. Các Coder hãy giúp BTC chọn các con đường cần xây dựng sao cho tổng chi phí là bé nhất nhé!

Chú ý: Các nút giao thông x1, x2, x3, ..., xk tạo thành một vòng đua nếu như ta có đường đi xi -> xi+1 -> xi+2 -> ... -> xi (1 <= i <= k).