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.