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.*;
import static java.lang.Math.*;

public class Main {
	public static void main( String args[] ) throws IOException {
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		PrintWriter pw = new PrintWriter( new BufferedWriter( new OutputStreamWriter( System.out ) ) );
		
		String s = "";
		while( (s=br.readLine()) != null ){
			int numEmp = Integer.parseInt(s);
			UFDS uf = new UFDS(numEmp);
			ArrayList<Employee> al = new ArrayList<Employee>();
			String[] t = br.readLine().trim().split(" ");
			
			PriorityQueue<Edge> pq = new PriorityQueue<Edge>(numEmp, new Comparator<Edge>() {
				@Override
				public int compare(Edge a, Edge b) {
					return a.w - b.w;
				}
			});
			
			for(int i = 0; i < numEmp; i++) {
				int q = Integer.parseInt(t[i]);
				al.add(new Employee(q, i+1));
			}		
			
			int connect = Integer.parseInt(br.readLine());
			while(connect-->0) {
				String[] u = br.readLine().trim().split(" ");
				int a = Integer.parseInt(u[0]);
				int b = Integer.parseInt(u[1]);
				int c = Integer.parseInt(u[2]);
				pq.offer(new Edge(a, b, c));
			}
			int minCost = 0;
			while(pq.size()>0) {
				Edge e = pq.poll();
				int v1 = e.u -1;
				int v2 = e.v -1;
				if(!uf.isSameSet(v1, v2) && al.get(v2).hasSuper()==false) {
					uf.unionSet(v1, v2);
					minCost+= e.w;
					al.get(v2).setSuper();
				}
				if(uf.numDisjointSets()==1) break;
			}
			if(uf.numDisjointSets()>1) pw.println("-1");
			else pw.println(minCost);
		}
		pw.close();
	}
	
	static class Edge {
		int u, v, w;
		public Edge( int u, int v, int w ){
			this.u = u;
			this.v = v;
			this.w = w;
		}
	}
	
	static class Employee {
		int qualification;
		int id;
		boolean hasSupervisor;
	
		public Employee(int q, int i) {
			qualification = q;
			id = i;
			hasSupervisor = false;
		}
		public boolean hasSuper() {
			return hasSupervisor;
		}
		public void setSuper() {
			hasSupervisor=true;
		}
	}

	static class UFDS {
		int[] f, rank, setSize;
		int numSets;
	
		public UFDS( int N ){
			f = new int[N];
			rank = new int[N];
			setSize = new int[N];
			Arrays.fill( f, -1 );
			Arrays.fill( rank, 0 );
			Arrays.fill( setSize, 1 );
			numSets = N;
		}
	
		public int findSet( int x ){
			if( f[x] == -1 ) return x;
			return f[x] = findSet( f[x] );
		}
	
		public boolean isSameSet( int a, int b ){
			return findSet(a) == findSet(b);
		}
		
		public void unionSet( int a, int b ){
			if( !isSameSet(a, b) ){
				--numSets;
				int x = findSet(a);
				int y = findSet(b);
				if( rank[x] > rank[y] ){
					f[y] = x;
					setSize[x] += setSize[y];
				}
				else{
					f[x] = y;
					setSize[y] += setSize[x];
					if( rank[x] == rank[y] )
						++rank[y];
				}
			}
		}
	
		public int numDisjointSets() { return numSets; }
		public int sizeOfSet( int i ) { return setSize[ findSet(i) ]; }
	}
}