Problem Statement

Mark’s company Facebook employed n coders .Now Mark needs to build a tree hierarchy of supervisor - subordinate relations in the company (this is to say that each employee, except one, has exactly one supervisor). There are m applications written in the following form:

Programmer p(i) is ready to become a supervisor of another programmer q(i) at extra cost r(i). The qualification aj of each employee is known, and for each of the application following is true: a(pi)>a(qi).(Here pi and qi are in subscript)

But since Mark is busy ,he needs your help to calculate the minimum cost of such a hierarchy, or find out whether it is impossible to build it.

Input

The first input line contains T – No of Test Case.(1 ≤ T ≤ 20)
For each test case input line contains an integer n (1 ≤ n ≤ 1000) – no of programmers in the company. The following line contains n space-separated integers a(j) (0 ≤ a(j) ≤ 10^6) — the programmer qualifications. The following line contains number m (0 ≤ m ≤ 10000) — amount of received applications. The following m lines contain the applications themselves, each of them in the form of three space-separated numbers: p(i) , q(i) and r(i) (1 ≤ p(i),q(i) ≤ n, 0 ≤ r(i) ≤ 10^6). Different applications can be similar, i.e. they can come from one and the same programmer who offered to become a supervisor of the same person but at a different cost!!! . For each application a(pi)>a(qi).

Output

For each test case output a single line — the minimum cost of building if there exist a hierarchy, or “-1” if it is impossible to build one..

It is guaranteed that all the answers will fit into long long

Explanation:

In the sample test case 1 :
One of the best possible ways to build a hierarchy is to take applications with indexes 1, 2 and 4, which give 11 as the total minimum cost.

In the sample test case 2:
it is impossible to build the required hierarchy, so the answer is -1.

SAMPLE INPUT
2
4
7 2 3 1
4
1 2 5
2 4 1
3 4 1
1 3 5
3
1 2 3
2
3 1 2
3 1 3

SAMPLE OUTPUT
11
-1

见题面

见题面