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 round17;


import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.StringReader;
import java.util.Arrays;
import java.util.Scanner;

public class B {
	private Scanner in;
	private PrintWriter out;
	
	int[][] r;
	int n;
	
	public void solve()
	{
		n = ni();
		int[] q = new int[n];
		for(int i = 0;i < n;i++)q[i] = ni();
		Pair[] ps = new Pair[n];
		for(int i = 0;i < n;i++){
			ps[i] = new Pair();
			ps[i].a = q[i];
			ps[i].b = i;
		}
		Arrays.sort(ps);
		
		int m = ni();
		int[] a = new int[m];
		int[] b = new int[m];
		int[] c = new int[m];
		r = new int[n][n];
		for(int i = 0;i < m;i++){
			a[i] = ni();
			b[i] = ni();
			c[i] = ni();
			if(r[a[i] - 1][b[i] - 1] > 0){
				r[a[i] - 1][b[i] - 1] = Math.min(r[a[i] - 1][b[i] - 1], c[i] + 1);
			}else{
				r[a[i] - 1][b[i] - 1] = c[i] + 1;
			}
		}
		
		int cost = 0;
		for(int i = 1;i < n;i++){
			// oyasagasi
			int min = Integer.MAX_VALUE;
			for(int j = 0;j < i;j++){
				if(r[ps[j].b][ps[i].b] > 0 && r[ps[j].b][ps[i].b] < min){
					min = r[ps[j].b][ps[i].b];
				}
			}
			if(min == Integer.MAX_VALUE){
				out.println(-1);
				return;
			}
			cost += min - 1;
		}
		out.println(cost);
	}
	
	private static class Pair implements Comparable<Pair>
	{
		public int a;
		public int b;
		
		@Override
		public int compareTo(Pair o) {
			return o.a - a;
		}
	}
	
	public void run() throws Exception
	{
//		in = new Scanner(new StringReader("4 7 2 3 1 4 1 2 5 2 4 1 3 4 1 1 3 5"));
//		in = new Scanner(new StringReader("4 7 2 3 1 4 1 2 5 2 4 1 3 4 1 1 3 0"));
//		in = new Scanner(new StringReader("3 1 2 3 2 3 1 2 3 1 3"));
		in = new Scanner(System.in);
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		out = new PrintWriter(System.out);
		
//		int n = in.nextInt();
		int n = 1;
		for(int i = 1;i <= n;i++){
			long t = System.currentTimeMillis();
			solve();
			out.flush();
//			System.err.printf("%04d/%04d %7d%n", i, n, System.currentTimeMillis() - t);
		}
	}
	
	
	public static void main(String[] args) throws Exception
	{
		new B().run();
	}
	
	private int ni() { return Integer.parseInt(in.next()); }
	private static void tr(Object... o) { System.out.println(o.length == 1 ? o[0] : Arrays.toString(o)); }
	private void tra(int[] a) {System.out.println(Arrays.toString(a));}
	private void tra(int[][] a)
	{
		for(int[] e : a){
			System.out.println(Arrays.toString(e));
		}
	}
	
}
