DMOPC '20 Contest 7 P5 - Mayors and Tolls

View as PDF

Submit solution

Points: 20
Time limit: 2.0s
Memory limit: 256M

Problem type

You are trying to make a profitable business from toll roads. There are currently M bidirectional roads between N cities, the j-th road connecting cities u_j and v_j. If you are able to turn the j-th road into a toll road, you will gain a profit of p_j.

However, you will only be able to buy a road between cities x and y if you have the approval of both mayors of the two cities. To gain the approval of the mayor of city i, you can pay them a "fee" of cost b_i. Once you have paid this "fee," the mayor will do their part to approve all roads neighbouring their city.

Overall, your net profit will be the sum of the profits from the roads minus the sum of the fees. What is the optimal net profit?


1 \le N \le 500

0 \le M \le 500

0 \le p_j, b_i \le 10^9

1 \le u_j, v_j \le N

u_j \ne v_j

Input Specification

The first line contains 2 integers N and M.

The second line contains N integers b_i (1 \le i \le N).

The next M lines each contain 3 integers u_j, v_j, and p_j.

Output Specification

Output the optimal net profit.

Sample Input

4 5
8 4 1 2
1 2 3
2 3 5
1 3 4
3 4 2
4 2 2

Sample Output



There are no comments at the moment.