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 Main {
	static FastReader sc=null;
	
	public static void main(String[] args) {
		sc=new FastReader();
		int n=sc.nextInt();
		person a[]=new person[n];
		for(int i=0;i<n;i++)a[i]=new person(sc.nextInt(),i);
		PriorityQueue<Edge> pq=new PriorityQueue<>();
		int m=sc.nextInt();
		Edge b[]=new Edge[m];
		for(int i=0;i<m;i++) {
			int v=sc.nextInt()-1,w=sc.nextInt()-1,cost=sc.nextInt();
			b[i]=new Edge(v,w,cost);
		}
		long ans=0;
		for(Edge e:b)pq.add(e);
		while(!pq.isEmpty()) {
			Edge e=pq.remove();
			if(!a[e.w].sub) {
				a[e.w].sub=true;
				ans+=e.cost;
			}
		}
		int c=0;
		for(person e:a)if(!e.sub)c++;
		System.out.println(c>1?-1:ans);
		
		
		
		
		
		
		
		
	}
	static class Edge implements Comparable<Edge>{
		int v,w,cost;
		Edge(int v,int w,int cost){
			this.v=v;
			this.w=w;
			this.cost=cost;
		}
		@Override
		public int compareTo(Edge o) {
			return this.cost-o.cost;
		}
		
	}
	static class person{
		int q,id;
		boolean sub;
		person(int q,int id){
			this.q=q;
			this.id=id;
			sub=false;
		}
	}
		
		
		
	static int[] ruffleSort(int a[]) {
		ArrayList<Integer> al=new ArrayList<>();
		for(int i:a)al.add(i);
		Collections.sort(al);
		for(int i=0;i<a.length;i++)a[i]=al.get(i);
		return a;
	}
	
	
	
	static void print(ArrayList<Integer> al) {
		for(int e:al) {
			System.out.print(e+" ");
		}
		System.out.println();
	}
	static void print(int a[]) {
		for(int e:a) {
			System.out.print(e+" ");
		}
		System.out.println();
	}
	static void print(long a[]) {
		for(long e:a) {
			System.out.print(e+" ");
		}
		System.out.println();
	}
	static long gcd(long a,long b) {
		if(b==0)return a;
		else return gcd(b,a%b);
	}
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
        int[] readArray(int n) {
    		int a[]=new int [n];
    		for(int i=0;i<n;i++) {
    			a[i]=sc.nextInt();
    		}
    		return a;
    	}
    } 
}






