전력공급

Bob이 살고 있는 Alberta 도시에는 $n$개의 건물이 있고 $1$번부터 $n$번까지 번호가 붙어있다. 각 건물은 일정량의 전기를 생산하고 소비한다. $v_i$는 $i$번째 빌딩의 전력 생산량에서 소비량을 뺀 값으로 해당 빌딩의 "잉여 전력"을 나타낸다. 만약 건물의 소비량이 생산량보다 크다면 $v_i$값은 음수가 된다. $v_i$가 0인 경우는 없고, 항상 정수이다.

일부 건물은 서로 전선으로 연결되어 있어서 한 건물에서 생산한 전력의 일부를 다른 건물에 보내주기도 한다. 현재 전선은 총 $m$개가 있고 $1$번부터 $m$번까지 번호가 붙어있다. $j$번째 전선은 건물 $x_j$에서 건물 $y_j$로 $z_j > 0$만큼의 전력을 공급해 준다. 각 전선은 방향성이 있고, 두 건물 사이에는 같은 방향의 전선은 최대 한 개만 있을 수 있다.

전기가 매우 중요한 자원이 되었기 때문에 Bob은 $n$개의 건물 중 일부 건물을 사들여 이 건물들의 잉여 전력 총량이 최대가 되도록 하고 싶다. 구체적으로, $S$가 $\{1, 2, \dots, n\}$의 부분집합일 때, 즉, Bob이 $S$에 속한 건물들을 사기로 했을 때, $S$의 잉여 전력 총량인 $V(S)$는 아래와 같이 정의 된다.

• ($S$에 속한 건물들의 잉여 전력 총합) - ($S$에 속한 건물들이 $S$에 속하지 않은 건물들에 전선을 통해 공급하는 전력의 총합)

예를 들어 $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$ 이라 하자.

• 건물 $1$은 자체 전력 생산량이 소비량보다 커서 잉여 전력이 $4$이며 다른 두 건물은 잉여 전력이 음수이다.
• $1$번 전선은 건물 $1$에서 건물 $2$로 $1$만큼의 전력을 공급한다.
• $2$번 전선은 건물 $2$에서 건물 $3$으로 $1$만큼의 전력을 공급한다.

이 예제에서 Bob이 건물을 살 방법은 총 $2^3 = 8$가지가 있는데, 각 경우에 대한 잉여 전력 총량은 아래와 같다.

• $S$가 공집합인 경우: $V(S) = 0$.
• $S = \{1\}$인 경우: $V(S) = 4 - 1 = 3$.
• $S = \{2\}$인 경우: $V(S) = (-1) - 1 = -2$.
• $S = \{3\}$인 경우: $V(S) = (-2) - 0 = -2$.
• $S = \{1, 2\}$인 경우: $V(S) = (4-1) - 1 = 2$. 이 경우, $1$번 전선의 경우 건물 $1$에서 건물 $2$로 전력을 공급하지만 두 건물 모두 사들인다면 위 정의에 따라 $V(S)$를 계산할 때 고려하지 않는다.
• $S = \{2, 3\}$인 경우: $V(S) = (-1-2) - 0 = -3$.
• $S = \{1, 3\}$인 경우: $V(S) = (4-2) - 1 = 1$.
• $S = \{1, 2, 3\}$인 경우: $V(S) = (4-1-2) - 0 = 1$.

$8$가지 방법 중 잉여 전력 총량이 최대가 되는 경우는 $S = \{1\}$인 경우이다.

다른 예로, $n = 2$, $m = 1$, $v_1 = 1$, $v_2 = -5$, $x_1 = 1$, $y_1 = 2$, $z_1 = 1$이라 하자.

• $S$가 공집합인 경우: $V(S) = 0$.
• $S = \{1\}$인 경우: $V(S) = 1 - 1 = 0$.
• $S = \{2\}$인 경우: $V(S) = -5$.
• $S = \{1, 2\}$인 경우: $V(S) = (1-5) - 0 = -4$.

총 $4$가지 방법 중 잉여 전력 총량이 최대가 되는 경우는 $S = \{1\}$ 또는 $S$가 공집합인 경우이다.

입력으로 $n$, $m$, $v$, $x$, $y$, $z$가 주어졌을 때, Bob이 달성할 수 있는 최대 잉여 전력 총량을 구해보자.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $n$과 $m$이 공백으로 구분되어 주어진다.

둘째 줄에는 각 건물의 잉여 전력량 $v_i$이 공백으로 구분되어 주어진다.

다음 $m$줄에 걸쳐 각 줄에 세 개의 정수 $x_j$, $y_j$, $z_j$주어진다. 이는 건물 $x_j$에서 건물 $y_j$로 $z_j$만큼의 전력이 공급되고 있음을 나타낸다.

각 테스트 케이스의 정답인 Bob이 달성할 수 있는 최대 잉여 전력량을 각 줄에 출력한다.

• $1 ≤ i ≤ n$인 모든 $i$에 대하여 $-100\,000 ≤ v_i ≤ 100\,000$ 이고 $v_i \ne 0$.
• $1 ≤ j ≤ m$인 모든 $j$에 대하여 $x_j \ne y_j$이고 $1 ≤ x_j, y_j ≤ n$, 그리고 $1 ≤ z_j ≤ 100\,000$.
• $1 ≤ j < k ≤ m$인 모든 $j$, $k$에 대하여 $x_j = x_k$이고 동시에 $y_j = y_k$인 경우는 없다. 즉, 모든 전선은 방향을 고려했을 때 고유하다.