17345번 - Maximum Profit 다국어

New technology is bombarding the mobile communications market. For major cellphone carriers, this is both an opportunity and a challenge. The THU Group's CS&T communications company is at the eve of a bloody battle in a new generation of communication technology. So much preparatory work needs to be done. For the site-selection aspect alone, they will need to complete prior market research, site investigation, optimization, and other projects.

After the market research and site investigation, the company has determined a total of N sites for relay stations of cellular signals. Due to geographical factors of these sites, establishing relay stations at different places require different principal costs. Luckily this cost data is already known after the prior market research: establishing the i-th relay station requires a principal cost of P_i (1 ≤ i ≤ N).

The company also researched the expected user base, consisting of M total customer groups. The i-th group's information can be summarized using the values A_i, B_i, and C_i. Users in this group will use relay stations A_i and B_i for communication, allowing the company to receive C_i in revenue (1 ≤ i ≤ M, 1 ≤ A_i, B_i ≤ N).

The THU Group's CS&T company can select a group of relay stations to establish (thus paying the necessary principal cost), servicing certain customer groups (thus receiving revenue). How must they select which relay stations to establish so that the company can receive the maximum possible profit? (Profit = total revenue − total principal cost)

The first line of input contains two integers N and M.

The second line contains N integers describing the principal cost to build each relay station, respectively P₁, P₂, …, P_N.

There will be M lines to follow. Line (i + 2) of input will contain 3 integers A_i, B_i, and C_i describing the information about the i-th customer group.

Your program should output a single integer, representing the maximum profit that the company can obtain.

N ≤ 5000, M ≤ 50000, 0 ≤ C_i ≤ 100, 0 ≤ P_i ≤ 100.