Migrated from Lutece 3194 宇宙市场趋势

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

星球的价值正在被重新计算……

「这个项目是否会说明，追回债务的益处是相互的？」
「但我们只需传达一个信息，就是宣告我们的存在。」
「它若是要有自己的价值，就得为公司增添价值。」

星际和平公司的战略投资部计划对某个星系进行投资。这个星系拥有 $n$ 颗星球，其中 $m$ 对存在潜在的贸易往来。

如果第 $i$ 对存在潜在贸易往来的两颗星球同时被战略投资部投资，那么战略投资部就可以从二者的贸易中得到 $r_i$ 的收益。投资第 $i$ 颗星球的成本是 $p_i$ 。

现在战略投资部想知道，如何进行投资才能使净利润（总收益 - 总投资）最大。

Input

第一行两个整数 $n$ 和 $m$ ，分别表示该星系的星球数量和存在潜在贸易往来的星球对数量。

第二行 $n$ 个整数，分别表示投资第 $i$ 颗星球的成本 $p_i$ 。

接下来 $m$ 行，每行三个整数 $u_i$ , $v_i$ 和 $r_i$ ，分别表示存在潜在贸易往来的星球和在它们之间进行贸易能带来的收益。

Output

一个整数，表示可获得的最大净利润。

Samples

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

5

Constraints

$2 \leq n \leq 5000$

$1 \leq m \leq 50000$

$0 \leq p_i,r_i \leq 100$

$1 \leq u_i,v_i \leq n$

Resources

2024 UESTC ICPC Training for Graph