Power Supply

In the city of Alberta where Bob lives there are $n$ buildings, numbered from $1$ to $n$. Each building produces and consumes a fixed amount of electricity. The value $v_i$ is the electricity produced by building $i$ minus the electricity it consumes, and it represents the building's "surplus power". If a building consumes more than it produces, $v_i$ is negative. No $v_i$ is 0, and every $v_i$ is an integer.

Some buildings are connected to each other by power lines, so part of the electricity produced by one building is sent to another building. There are $m$ power lines in total, numbered from $1$ to $m$. The $j$-th power line supplies $z_j > 0$ units of power from building $x_j$ to building $y_j$. Each power line has a direction, and between two buildings there is at most one power line in the same direction.

Since electricity has become a very important resource, Bob wants to buy some of the $n$ buildings so that the total surplus power of these buildings is maximized. Specifically, when $S$ is a subset of $\{1, 2, \dots, n\}$, that is, when Bob decides to buy the buildings in $S$, the total surplus power $V(S)$ of $S$ is defined as follows.

• (the total surplus power of the buildings in $S$) - (the total power that the buildings in $S$ supply through power lines to buildings not in $S$)

For example, let $n = 3$, $m = 2$, $v_1 = 4$, $v_2 = -1$, $v_3 = -2$, $x_1 = 1$, $x_2 = 2$, $y_1 = 2$, $y_2 = 3$, $z_1 = 1$, $z_2 = 1$.

• Building $1$ produces more electricity than it consumes, so its surplus power is $4$, while the other two buildings have negative surplus power.
• Power line $1$ supplies $1$ unit of power from building $1$ to building $2$.
• Power line $2$ supplies $1$ unit of power from building $2$ to building $3$.

In this example there are $2^3 = 8$ ways for Bob to buy buildings, and the total surplus power for each case is as follows.

• If $S$ is the empty set: $V(S) = 0$.
• If $S = \{1\}$: $V(S) = 4 - 1 = 3$.
• If $S = \{2\}$: $V(S) = (-1) - 1 = -2$.
• If $S = \{3\}$: $V(S) = (-2) - 0 = -2$.
• If $S = \{1, 2\}$: $V(S) = (4-1) - 1 = 2$. Here, power line $1$ supplies power from building $1$ to building $2$, but since Bob buys both buildings, it is not counted when computing $V(S)$ according to the definition above.
• If $S = \{2, 3\}$: $V(S) = (-1-2) - 0 = -3$.
• If $S = \{1, 3\}$: $V(S) = (4-2) - 1 = 1$.
• If $S = \{1, 2, 3\}$: $V(S) = (4-1-2) - 0 = 1$.

Among the $8$ ways, the total surplus power is maximized when $S = \{1\}$.

As another example, let $n = 2$, $m = 1$, $v_1 = 1$, $v_2 = -5$, $x_1 = 1$, $y_1 = 2$, $z_1 = 1$.

• If $S$ is the empty set: $V(S) = 0$.
• If $S = \{1\}$: $V(S) = 1 - 1 = 0$.
• If $S = \{2\}$: $V(S) = -5$.
• If $S = \{1, 2\}$: $V(S) = (1-5) - 0 = -4$.

Among the $4$ ways, the total surplus power is maximized when $S = \{1\}$ or when $S$ is the empty set.

Given $n$, $m$, $v$, $x$, $y$, $z$ as input, find the maximum total surplus power Bob can achieve.

The first line gives the number of test cases $T$.

The first line of each test case gives $n$ and $m$, separated by a space.

The second line gives the surplus power $v_i$ of each building, separated by spaces.

The following $m$ lines each give three integers $x_j$, $y_j$, $z_j$. This means that $z_j$ units of power are being supplied from building $x_j$ to building $y_j$.

For each test case, print the maximum total surplus power Bob can achieve on its own line.

• For every $i$ with $1 ≤ i ≤ n$, $-100\,000 ≤ v_i ≤ 100\,000$ and $v_i \ne 0$.
• For every $j$ with $1 ≤ j ≤ m$, $x_j \ne y_j$, $1 ≤ x_j, y_j ≤ n$, and $1 ≤ z_j ≤ 100\,000$.
• For every $j$, $k$ with $1 ≤ j < k ≤ m$, there is no case where $x_j = x_k$ and $y_j = y_k$ at the same time. That is, all power lines are distinct when direction is taken into account.