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.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.nio.file.attribute.FileOwnerAttributeView;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;









public class Main{
    static class MyScanner {
    	BufferedReader br; 
        StringTokenizer st; 
  
        public MyScanner() 
        { 
            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; 
        }  
    }
        
    
         public static void main(String[] args) throws IOException {
                PrintWriter out = new PrintWriter(System.out);
                MyScanner sc = new MyScanner();
                Main solver = new Main();
                solver.solve(out, sc);
                out.flush();
                out.close();
                
        }
  
         
         
      
      
       
     
        
        
      
        List<Integer>[] g; 
        boolean[] v;
        boolean[] vv;
        int[] parent;
        int[] size;
        void solve(PrintWriter out, MyScanner sc) throws IOException{    
      
        	int n = sc.nextInt();
        	g = new ArrayList[n];
        	int[] q = new int[n];
        	for(int i = 0; i < n ; ++i) q[i] = sc.nextInt();
        	for(int i = 0; i < n ; ++i) g[i] = new ArrayList<>();       		
       
        	int m = sc.nextInt();
        	Edge[] app = new Edge[m];
        	int[] root = new int[n];
        	for(int i = 0 ; i < m ; ++i) {
        		
        		int a = sc.nextInt() - 1;
        		int b = sc.nextInt() - 1;
        		int c = sc.nextInt();
        		app[i] = new Edge(a, b, c);
        		root[b]++;
        		g[a].add(b);
        		
        				
        	}
        	
        	int c = 0;
        	int r = -1;
        	for(int i = 0; i < n ; ++i	) {
        		if(root[i] == 0) {
        			++c;
        			r = i;
        		}
        	}
        	if(c != 1) {
        		out.print(-1);return;
        	}
        	
        	v = new boolean[n];
        	vv = new boolean[n];
        	int comp = 0;
        	dfs(r);
        	for(int i = 0; i < n ; ++i) {
        		if(!v[i]) {
        			out.print(-1);return;
        		}
        	}
        	
        	
        	long cost = 0;
        	parent = new int[n];
        	size = new int[n];
        	
        	for(int i = 0; i < n ; ++i) {
        		parent[i] = i;
        		size[i] = 1;
        	}
        	Arrays.sort(app, (e1 , e2) -> e1.c - e2.c);
        	for(int i = 0; i < m ; ++i) {
        		
        		if(vv[app[i].b]) continue;
        		int a = find(app[i].a);
        		int b = find(app[i].b);
        		if(a != b) {
        			cost += app[i].c;
        			vv[app[i].b] = true;
        			union(app[i].a, app[i].b);
        		}
        		
        	}
        	out.print(cost);
        
        	
        	
        	
        	
        	
        	
        }
        
        int find(int v) {
        	if(parent[v] == v) return v;
        	return parent[v] = find(parent[v]);
        }
        
        void union(int a, int b) {
        	
        	if(size[a] < size[b]) {
        		size[a] += size[b];
        	}else {
        		parent[a] = parent[b];
        		size[b] += size[a];
        	}
        }
        
        void dfs(int n) {
        	v[n] = true;
        	for(int k : g[n]) {
        		if(!v[k]) dfs(k);
        	}
        }
        
        class Edge{
        	int a, b, c;
        	public Edge(int a, int b, int c) {
        		this.a = a;
        		this.b = b;
        		this.c = c;
        	}
        }
        
       
        
       
        
       
 }