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();
                
        }
  
         
         
      
      
       
     
        
        
      
       
        void solve(PrintWriter out, MyScanner sc) throws IOException{    
        	
        	int n = sc.nextInt();
        	int[] q = new int[n];
        	for(int i = 0; i < n ; ++i) q[i] = sc.nextInt();
        	
        	int m = sc.nextInt();
        	int[] best = new int[n];
        	Arrays.fill(best, Integer.MAX_VALUE);
        	
        	for(int i = 0; i < m ; ++i) {
        		int a = sc.nextInt() - 1;
        		int b = sc.nextInt() - 1;
        		int c = sc.nextInt();
        		best[b] = Math.min(best[b], c);
        	}
        	
        	int res = 0;
        	long cost = 0;
        	for(int i = 0; i < n ; ++i) {
        		if(best[i] == Integer.MAX_VALUE) ++res;
        		cost += best[i];
        	}
        	
        	if(res != 1) out.print(-1);
        	else {
        		cost -= Integer.MAX_VALUE;
        		out.print(cost);
        	}
        	
        }
        
      
        
       
        
       
        
       
 }