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?

Constraints

$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

2