The once dominant airline Burgmanistan And Southern Menzico Airline Service (BASMAS) is in some strife. Despite a recent international codeshare agreement, staff layoffs and a new Titanium Zero frequent flyer status level, the airline has not recovered from the drop of its perfect safety record, staff strikes and competing low-cost carriers. Overall revenue is plummeting. In order to save the airline, BASMAS CEO Joy Alance has employed your consulting firm to save money by cancelling un-necessary costly flight routes.
BASMAS operates M flight routes. Each flight route connects two of the N cities that BASMAS services, and has a cost of operation. Each city is in a certain country. BASMAS guarantees its customers that:
It is critical that BASMAS maintains these two guarantees after cancelling flight routes.
You will be given the country of each city that BASMAS services and the list of BASMAS flight routes - for each one the two cities that it connects and the total cost to BASMAS of operating the route.
Your task is to find the maximum operating costs the company can save by cancelling routes while maintaining the two conditions described above.
Output should consist of one line with one integer: the maximum sum of costs of flight routes that can be cancelled without breaking the two described conditions of BASMAS service.
5 6 1 1 1 4 4 1 2 10 1 3 40 3 2 20 2 4 50 3 5 55 5 4 80
In this example, we can cut the flight route between 1 and 3 to save $40, and the route between 3 and 5 to save $55. (Note that the two countries in this example are labelled 1 and 4 - countries might not be given consecutive labels).
For all subtasks, 1 ≤ M ≤ 100,000 and each flight route will have a cost between 1 and 10,000.