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

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 always possible to travel between any two cities by taking one or
more BASMAS flights.
- It is always possible to travel between any two cities in the same
country without needing to pass through a city in a different country.

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.

- The first line of input will contain two space-separated integers N and M.
- The following N lines will each contain one integer, the ith representing
the country of city i. Each country will be labelled with some integer between
1 and N.
- The following M lines will each contain three integers a
_{i}, b_{i}, c_{i}representing a flight route between cities a_{i}and b_{i}(a_{i}b_{i}, 1 ≤ a_{i}, b_{i}≤ N) with cost c_{i}. No pair of cities will appear more than once in this list (that is, there is at most one direct flight route between any two cities).

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

95

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.

- For Subtask 1 (40 points), all cities will be in the same country and 2
≤ N ≤ 1000.
- For Subtask 2 (40 points), 2 ≤ N ≤ 1000.
- For Subtask 3 (20 points), 2 ≤ N ≤ 100,000.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 22 May 2022, 10:56am AEST