Optimal Relay Station Selection

In the evolving mobile communications market, THU Group's CS&T Communications company is about to enter the next‐generation communications technology battle. After completing market research and site surveys, the company has identified N potential locations for building relay stations. Each station i requires a cost of \(P_i\) to be built (\(1 \le i \le N\)).

Furthermore, there are M targeted user groups. For the j-th user group, the information is given by three integers \(A_j\), \(B_j\), and \(C_j\). Users in this group will communicate through stations \(A_j\) and \(B_j\), and if both stations are built, the company earns a benefit of \(C_j\) (\(1 \leq j \leq M\) and \(1 \le A_j, B_j \le N\)).

The company can choose a subset of relay stations to build. The net profit is the sum of benefits from all user groups that have both corresponding stations built, minus the total cost of building the stations. Formally, if we denote by \(S\) the set of built stations, the net profit is

[ \text{Profit} = \sum_{j=1}^{M} C_j \cdot \mathbf{1}{A_j \in S \text{ and } B_j \in S} - \sum_{i \in S} P_i. ]

Your task is to choose a subset \(S\) of relay stations such that the net profit is maximized. Note that if no station is built, the profit is 0.

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of potential relay station locations and the number of user groups, respectively.

The second line contains \(N\) integers: \(P_1, P_2, \ldots, P_N\), where \(P_i\) is the cost to build the \(i\)-th relay station.

Each of the following \(M\) lines contains three integers \(A_j\), \(B_j\), and \(C_j\) describing that if both station \(A_j\) and station \(B_j\) are built, the company earns a benefit of \(C_j\) from the j-th user group.

outputFormat

Output a single integer, the maximum net profit that can be achieved.

sample

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

2