Nick's company employed n people. Now Nick needs to build a tree hierarchy of «supervisor-surbodinate» 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: «employee ai is ready to become a supervisor of employee bi at extra cost ci». The qualification qj of each employee is known, and for each application the following is true: qai > qbi. 

Would you help Nick calculate the minimum cost of such a hierarchy, or find out that it is impossible to build it.

Input

The first input line contains integer n (1 ≤ n ≤ 1000) — amount of employees in the company. The following line contains n space-separated numbers qj (0 ≤ qj ≤ 106)— the employees' 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: ai, bi and ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 106). Different applications can be similar, i.e. they can come from one and the same employee who offered to become a supervisor of the same person but at a different cost. For each application qai > qbi.

Output

Output the only line — the minimum cost of building such a hierarchy, or -1 if it is impossible to build it.

Examples

Input

4
7 2 3 1
4
1 2 5
2 4 1
3 4 1
1 3 5


Output

11


Input

3
1 2 3
2
3 1 2
3 1 3


Output

-1

Note

In the first sample one of the possible ways for building a hierarchy is to take applications with indexes 1, 2 and 4, which give 11 as the minimum total cost. In the second sample it is impossible to build the required hierarchy, so the answer is -1.
// package Incomplete;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;
import java.io.InputStreamReader;

public class Main {
	static final BufferedReader br =new BufferedReader(new InputStreamReader(System.in)); 
	public static void main(String args[]) throws java.lang.Exception	{		 
		int n = Integer.parseInt(br.readLine());
		String qualification[] = br.readLine().split(" ");
		HashMap<Integer, ArrayList<Integer>> outmap = new HashMap<>();
		for (int i = 1; i<= n;i++)
			outmap.put(i, new ArrayList<Integer>());
		int costs[][] = new int[n+1][n+1];
		for (int i = 1; i<= n; i++)
			for (int j = 1; j<= n; j++)
				costs[i][j]  = -1;
		int bosses[] = new int[n+1];
		int m = Integer.parseInt(br.readLine());
		for (int it = 1; it <= m; it++) {
			String edge[] = br.readLine().split(" ");
			int boss = Integer.parseInt(edge[0]);
			int subordinate = Integer.parseInt(edge[1]);
			int cost = Integer.parseInt(edge[2]);
			if (costs[boss][subordinate] == -1)costs[boss][subordinate] = cost;
			else {
				if (costs[boss][subordinate] > cost)costs[boss][subordinate] = cost;
			}
			ArrayList<Integer> temp = outmap.get(subordinate);
			temp.add(boss);
			outmap.put(subordinate, temp);
		}
		int count = 0;
		Iterator<Integer> it = outmap.keySet().iterator();
		while (it.hasNext() && count != 2) {
			if (outmap.get(it.next()).size() == 0)count++;
		}
		if (count == 2)
			System.out.println("-1");
		else {
			Set<Integer> set = outmap.keySet();
			for (int key: set) {
				ArrayList<Integer> list = outmap.get(key);
				if (list.size() == 0)bosses[key] = -1;
				if (list.size() == 1)bosses[key] = list.get(0);
				if (list.size() > 1) {
					int min = Integer.MAX_VALUE;
					for (int j = 0 ; j < list.size(); j++) {
//						System.out.println("boss = "+list.get(j));
//						System.out.println("subordinate = "+key);
						int thiscost = costs[list.get(j)][key];
						if (min > thiscost) {
							min = thiscost;
							bosses[key] = list.get(j);
						}
					}
//					System.out.println(min);
				}
			}
//			System.out.println(outmap);
//			System.out.println(Arrays.toString(bosses));
//			System.out.println();
//			for (int i = 0; i <= n; i++)System.out.println(Arrays.toString(costs[i]));
			int total = 0;
			for (int i = 1;i <= n; i++) {
				if (bosses[i]!= -1) {
					total += costs[bosses[i]][i];
				}
			}
			System.out.println(total);
		}
	}
}