AIOC Banner

Problem: Flight Planning II

Want to try solving this problem? You can submit your code online if you log in or register.


Flight Planning II: BASMAS

Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 128 MB

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.

Input

Output

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.

Sample Input

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

Sample Output

95

Explanation

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).

Subtasks

For all subtasks, 1 ≤ M ≤ 100,000 and each flight route will have a cost between 1 and 10,000.

 


Privacy statement
© Australian Mathematics Trust 2001-2021

Contact: training@orac.amt.edu.au
Page generated: 21 September 2021, 10:06am AEST