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.
import java.io.*;
import java.util.*;

public class CF17B {
	public static BufferedReader buffstdin = new BufferedReader(new InputStreamReader(System.in));
	static OutputStream out = new BufferedOutputStream ( System.out );
	
	public static void Sprintln(Object s) throws IOException {
		String S = s + "";
		System.out.println(S);
	}
	public static void Sprint(Object s) throws IOException {
		System.out.print("" + s);
	}
	public static void println(Object s) throws IOException {
		String S = s + "\n";
		out.write(S.getBytes());
	}
	public static void println() throws IOException {
		out.write("\n".getBytes());
	}
	public static void print(Object s) throws IOException {
		out.write(("" + s).getBytes());
	}
	public static int Int(String s) {
		return Integer.parseInt(s);
	}
	public static String[] getLine() throws IOException {
		return buffstdin.readLine().trim().split(" ");
	}
	public static String getString() throws IOException {
		return buffstdin.readLine().trim();
	}
	public static int getInt() throws IOException {
		return Int(getString());
	}
	public static int[] getIntLine() throws IOException {
		String[] line = buffstdin.readLine().trim().split(" ");
		int[] a = new int[line.length];
		for(int i : range(line.length))	a[i] = Int(line[i]);
		return a;
	}
	public static int[] range(int u) {
		int[] array = new int[u];
		for(int i=0; i<u; i++) array[i] = i;
		return array;
	}
	public static int[] range(int l, int u) {
		int[] array = new int[u-l];
		for(int i=0; i<u-l; i++) array[i] = l+i;
		return array;
	}
	
	public static int[] quals;
	public static int[] cost;
	public static int[][] abc;
	public static final int a = 0;
	public static final int b = 1;
	public static final int c = 2;
	public static final int MAXCOST = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		int totalCases = getInt();
		quals = getIntLine(); //ignore this
		cost = new int[quals.length+1]; //adjust for the damned 1-based indexing
		for(int k : range(cost.length)) {
			cost[k] = MAXCOST;
		}
		int applications = getInt();
		
		/*if(applications < totalCases) { yeah this isn't a real thing. 
			Sprintln("-1");
			return;
		}*/
		
		abc = new int[applications][3];
		//Sprintln(applications);
		for(int i : range(applications)) {
			abc[i] = getIntLine();
			//Sprintln(i);
			int A = abc[i][a];
			int B = abc[i][b];
			int C = abc[i][c]; //why am I using a 2d array and constants? It's just confusing
			if(cost[B] > C) { //if cost of supervision < current cost, be greedy and hire the guy
					cost[B] = C;
			}
		}
		
		int noSups = 0;
		int totalcost = 0;
		for(int i : range(1,totalCases+1)) { //1-based indexing, grumble grumble grumble grumble grumble
			if(cost[i] == MAXCOST) {
				noSups++;
			}
			else {
				totalcost+=cost[i];
			}
		}
		/*for(int i=0; i<cost.length; i++) {
			System.out.println(i + " " + cost[i]);
		}*/
		//Sprintln(noSups);
		if(noSups != 1) { //2 because 0
			print("-1");
		}
		else {
			print(totalcost);
		}
		out.flush();
	}
}
