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

public class Task {

	public static void main(String[] args) throws Exception {

		new Task().solve();
	}
	
	
	void solve() throws Exception {
		Reader in = new Reader("1.in");
		PrintWriter out = new PrintWriter( new BufferedWriter( new OutputStreamWriter(System.out) ) );
		
		
		int n = in.nextInt();
		int[][] g = new int[n+1][n+1];
		
		for (int i = 0; i < n; i++) {
			int x = in.nextInt();
		}
		
		int m = in.nextInt();
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				g[i][j] = -1;
			}
		}
		
		for (int i = 0; i < m; i++) {
			int x = in.nextInt()-1;
			int y = in.nextInt()-1;
			int w = in.nextInt();
			if (g[x][y] != -1)
				g[x][y] = Math.min(g[x][y], w);
			else
				g[x][y] = w;
		}
		
		int s = -1;
		
		for (int i = 0; i < n; i++) {
			boolean f = true;
			int j = 0;;
			for (j = 0; j < n; j++) {
				if (g[j][i] != -1)
				{
					f = false;
					break;
				}	
			}
			if (f) {
				s = i;
				break;
			}
		
		}
		
		int[] d = new int[n];
		Arrays.fill(d, Integer.MAX_VALUE);
		d[s] = 0;
		boolean u[] = new boolean[n];
		
		for (;;) {
			int v = -1;
			for (int i = 0; i < n; i++)
					if ((v == -1 || d[i] < d[v]) && !u[i])
						v = i;
			
			if (v == -1 || d[v] == Integer.MAX_VALUE) break;
			
			u[v] = true;
			
			for (int i = 0; i < n; i++)
				if (g[v][i] != -1 && d[i] > g[v][i]) {
					d[i] = g[v][i];
				}
		}
			
		boolean ans = true;
		int sum = 0;

		for (int i = 0; i < u.length; i++) {
			
			if (!u[i]) {
				sum = -1;
				ans = false;
				break;
			}
			sum += d[i];
		}
		
		if (!ans) sum = -1;
		
		out.println(sum);
		out.flush();
		out.close();
		
	}
	
	class Pair implements Comparable<Pair>{
		int i;
		int a;
		Pair(int i, int a) {
			this.i = i;
			this.a = a;
		}
		@Override
		public int compareTo(Pair pair) {
			return a > pair.a ? -1: a < pair.a ? 1: 0;
		}
	}
	
	class DSU {
		
		int size;
		int[] sz;
		int[] set;
		
		DSU(int size) {
			this.size = size;
			set = new int[size+1];
			sz = new int[size+1];
			for(int i = 0; i < size; i++) {
				set[i] = i;
				sz[i] = 1;
			}
		}
		
		int get(int x) {
			if (set[x] == x)
				return x;
			else
				return set[x] = get(set[x]);
		}
		
		void union(int x, int y) {
				x = get(x);
				y = get(y);
				if (sz[x] < sz[y]) {
					set[x] = y;
					sz[y] += sz[x];
				}	
				else
				{	
					set[y] = x;
					sz[x] += sz[y];
				}				

		}
		
		boolean incomp(int x, int y) {
			return get(x) == get(y);
		}
		
		int getSize(int x) {
			x = get(x);
			return sz[x];
		}
		
	}
	
	class Reader {
		
		BufferedReader br;
		StringTokenizer token = null;
		
		Reader(String file) throws Exception {
			br = new BufferedReader( new InputStreamReader(System.in) );
			
		}
		
		String next() throws Exception {
			while (token == null || !token.hasMoreElements()) {
				token = new StringTokenizer(br.readLine());
			}
			return token.nextToken();
		}
		
		int nextInt() throws Exception {
			return Integer.parseInt(next());
		}
		
		long nextLong() throws Exception {
			return Long.parseLong(next());
		}
		
		double nextDouble() throws Exception {
			return Double.parseDouble(next());
		}
		
	}

}
