Migrated from Lutece 223 Food

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

As a young teacher in a kindergarten, you are charged with the task to disperse food among children. Some child may ask to receive certain amount of food more or less than another child. For example, maybe A asks for $20$ grams more than B has. What’s more, each child should receive certain amount of food at least so that he or she won’t starve. Now given the requirement, you should figure out at least how much food should be distributed.

Input

First line contains an integer $T$, the number of test cases;

Each test case begin with two integers, $N$, the number of children and $M$, the number of requirement. $0 < N \leq 20000, 0 \leq M \leq 100000$

The following line contains $N$ integers, the amount of food each child should receive at least, which is less than $1000$.

The following $M$ lines each specify a requirement. Each line contains three integers $A, B, C$. specifying that the child with number $A$ should receive $C$ grams more than the child with number $B$ receives. Children are numbered from $0$ to $N-1$. Requirement contradicts with previous ones should be dismissed. $0 \leq A < N, 0 \leq B < N, -20 \leq C \leq 20$.

Output

For each test case print one line with the minimum amount of food.

Samples

2
3 3
8 6 10
0 1 5
0 1 -3
0 2 4
4 4
11 20 9 18
1 0 5
3 2 7
1 2 -8
3 0 10

33
98

Resources

第四届北京邮电大学程序设计竞赛网络预赛