1723 - Stations

Time Limit : 1 Second

Memory Limit : 256 MB

Submission: 7

Solved: 2


After stuck in a traffic jam millions of times in Wuhan, zf decided to re-planning bus lines.

First there are N alternative stations determined by the experts, each station needs maintenance costs Pi,

After investigation he found that there are M user groups, often going from the Ai station to the Bi station, can provide Ci earnings.

Now, boss zf would like to know, the maximum profit is how much? (the sum of the earnings minus the sum of the costs)


There are multiple sets of data for this question.

Each set of data T <= 10

The first row of each set of data is two positive integers N and M.

The second line has N integersP1, P2, ..., PNdescribing the cost of building each station.

The next M rows, Ai, Bi and Ci in the (i + 2) th row describe the information of the i-th user group.

The meaning of all variables can be found in the description.


Outputs an integer for each set of data, indicating the maximum profit that the company can get.

sample input
5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3
sample output
© 2015 HUST ACMICPC TEAM. All Right Reserved.