Heroes Never Die

Time limit2sMemory limit512 MB

Summary

Choose a subset of heroes to revive, gaining bond rewards when both endpoints are chosen, to maximize total reward minus revival cost.

Level: Hard8 of 10
Topics: Graph, Minimum spanning tree, Greedy, Union-find
Solved: No attempts yet

Problem

Every hero has fallen, and Mercy says: "Heroes never die."

Reviving hero $i$ costs $P(i)$ energy. Two heroes can be linked by a bond, and when both heroes of a bond are revived, that bond returns $C(i)$ energy.

If Mercy revives $K$ heroes ( $0 \le K \le N$ ), she gains the total energy returned by the bonds whose two heroes are both revived, minus the total energy spent on reviving them. Find the largest amount of energy Mercy can gain.

$K = 0$ is a valid choice, so the answer is never negative.

Input

The first line contains the number of heroes $N$ ( $1 \le N \le 5000$ ) and the number of bonds $M$ ( $0 \le M \le 50000$ ), separated by a space.

The second line contains $P(1), P(2), \dots, P(N)$ , the energy needed to revive each hero.

Each of the next $M$ lines contains one bond as $A(i)\ B(i)\ C(i)$ . $A(i)$ and $B(i)$ are distinct hero numbers between 1 and $N$ , and the same pair may appear in more than one bond. $P(i)$ and $C(i)$ are integers between 0 and 100.

Output

Print the largest amount of energy Mercy can gain, on one line.

Examples9

Example 1

Input

Expected output

Example 2
Input
```
1 0
0
```
Expected output
```
0
```
Example 3
Input
```
1 0
100
```
Expected output
```
0
```
Example 4
Input
```
2 1
100 100
1 2 100
```
Expected output
```
0
```
Example 5
Input
```
2 1
10 20
1 2 100
```
Expected output
```
70
```
Example 6
Input
```
3 3
0 0 0
1 2 0
2 3 0
1 3 0
```
Expected output
```
0
```

Example 7

Input

4 3
100 100 1 1
1 2 100
1 2 100
3 4 5

Expected output

Example 8

Input

6 6
5 5 5 100 100 100
1 2 6
2 3 6
1 3 6
4 5 100
5 6 100
4 6 100

Expected output

Example 9

Input

Expected output