CF1082G.Petya and Graph

Petya has a simple graph (that is, a graph without loops or multiple edges) consisting of $n$ vertices and $m$ edges.

The weight of the $i$-th vertex is $a_i$.

The weight of the $i$-th edge is $w_i$.

A subgraph of a graph is some set of the graph vertices and some set of the graph edges. The set of edges must meet the condition: both ends of each edge from the set must belong to the chosen set of vertices.

The weight of a subgraph is the sum of the weights of its edges, minus the sum of the weights of its vertices. You need to find the maximum weight of subgraph of given graph. The given graph does not contain loops and multiple edges.

佩蒂亚有一个简单图（即不含自环和重边的图），该图包含 $n$ 个顶点和 $m$ 条边。

第 $i$ 个顶点的权值为 $a_i$。

第 $i$ 条边的权值为 $w_i$。

图的一个子图是指图中某些顶点的集合以及某些边的集合，且需满足如下条件：该边集合中的每条边的两个端点都必须属于所选的顶点集合。

子图的权值定义为：其所有边的权值之和减去其所有顶点的权值之和。你需要求出给定图的所有子图中权值的最大值。给定图不含自环和重边。

The first line contains two numbers $n$ and $m$ ($1 \le n \le 10^3, 0 \le m \le 10^3$) - the number of vertices and edges in the graph, respectively.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) - the weights of the vertices of the graph.

The following $m$ lines contain edges: the $i$-e edge is defined by a triple of integers $v_i, u_i, w_i$ ($1 \le v_i, u_i \le n, 1 \le w_i \le 10^9, v_i \neq u_i$). This triple means that between the vertices $v_i$ and $u_i$ there is an edge of weight $w_i$. It is guaranteed that the graph does not contain loops and multiple edges.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^3,\ 0 \le m \le 10^3$），分别表示图中的顶点数和边数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示图中各顶点的权值。

接下来的 $m$ 行描述边：第 $i$ 条边由三个整数 $v_i, u_i, w_i$（$1 \le v_i, u_i \le n,\ 1 \le w_i \le 10^9,\ v_i \neq u_i$）定义。该三元组表示顶点 $v_i$ 与 $u_i$ 之间存在一条权值为 $w_i$ 的边。保证图中不含自环和重边。

Print one integer — the maximum weight of the subgraph of the given graph.

输出一个整数——给定图的子图的最大权重。

In the first test example, the optimal subgraph consists of the vertices ${1, 3, 4}$ and has weight $4 + 4 + 5 - (1 + 2 + 2) = 8$. In the second test case, the optimal subgraph is empty.

在第一个测试样例中，最优子图包含顶点 $\{1, 3, 4\}$，其权重为 $4 + 4 + 5 - (1 + 2 + 2) = 8$。在第二个测试用例中，最优子图为空。