P4174 [NOI2006] Maximum Profit

New technologies are impacting the mobile communications market. For major operators, this is both an opportunity and a challenge. On the eve of the battle over next-generation communication technologies, the CS&T Communications company under the THU Group has a lot to prepare. Even for site selection alone, they need to complete preliminary market research, site surveys, and optimization. After the preliminary market research and site surveys, the company has identified a total of $N$ candidate locations for communication relay stations. Due to geographical differences, the cost of building a relay station varies by location. Fortunately, after the preliminary investigation, these data are known: the cost to build the $i$-th relay station is $P_i$ ($1 \leq i \leq N$). In addition, the company has identified all target user groups, a total of $M$. The information for the $i$-th user group is summarized by $A_i$, $B_i$, and $C_i$: these users will use relay station $A_i$ and relay station $B_i$ to communicate, and the company can gain a profit of $C_i$ ($1 \leq i \leq M$, $1 \leq A_i, B_i \leq N$). The CS&T company under THU can choose to build some relay stations (incurring costs), serve some user groups, and obtain revenue (the sum of gains). How should the company choose which relay stations to build to maximize net profit? (Net profit = sum of gains − sum of costs.)

The first line of the input contains two positive integers $N$ and $M$. The second line contains $N$ integers describing the construction cost of each relay station, in order: $P_1 , P_2 , …,P_N$. The following $M$ lines: the $(i + 2)$-th line contains three numbers $A_i$, $B_i$, and $C_i$ describing the information of the $i$-th user group. All variables have the meanings described in the problem statement.

Output a single integer, representing the maximum net profit the company can obtain.

Example: choose to build relay stations $1, 2, 3$. The total cost is $6$, and the total gain is $10$, so the maximum profit is $4$. For $100\%$ of the testdata: $N \leq 5\,000$, $M \leq 50\,000$, $0 \leq C_i \leq 100$, $0 \leq P_i \leq 100$. Translated by ChatGPT 5