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

import java.io.*;         
import java.util.*;         
import java.math.*;         

 
public class Main  implements Runnable {
//public static final String FileName = "test";
StreamTokenizer ST;      
PrintWriter out;      
BufferedReader br;   
Scanner in;
static final int inf = 1000000000+10;
 
int nextInt() throws IOException{      
    ST.nextToken();      
    return (int)ST.nval;      
}
long nextLong() throws IOException{      
    ST.nextToken();      
    return (long)ST.nval;      
}      
String next() throws IOException{      
    ST.nextToken();      
    return ST.sval;      
}      
double nextD() throws IOException{      
    ST.nextToken();      
    return ST.nval;      
}      
public static void main(String[] args) throws IOException {       
   new Thread(new Main()).start();
//  new Main().run();
}
 
public void run()  {      
    try {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));      
        //br = new BufferedReader(new FileReader(new File(FileName+".in")));
        //out = new PrintWriter(new BufferedWriter(new FileWriter(FileName+".out")));
        in = new Scanner(br);
        ST = new StreamTokenizer(br);      
        solve();      
        out.close();
        //in.close();
        br.close();   
    }         
    catch (IOException e) {       
        e.printStackTrace();
        throw new IllegalStateException(e);  
    }      
}


public void solve() throws IOException {
    int n = nextInt();
    for (int i=0; i<n; i++) nextInt();
    int m = nextInt();
    int[][] a = new int[n][n];
    int[] d1 = new int[n];
    int[] d2 = new int[n];
    for (int[] aa:a) Arrays.fill(aa, -1);
    while (m-->0) {
        int x = nextInt()-1;
        int y = nextInt()-1;
        int cost = nextInt();
        if (a[x][y]<0) { 
            a[x][y] = cost; 
            d1[x]++;
            d2[y]++;
        } else a[x][y] = Math.min(a[x][y], cost);       
    }               
    int res = 0, cnt = 0;
    for (int i=0; i<n; i++) {
        int min = inf;
        for (int j=0; j<n; j++)
            if (a[j][i]>=0 && a[j][i]<=min) min = a[j][i];
        if (min==inf) cnt++; else res += min;
    }
    if (cnt==1) out.print(res); else out.print(-1);
    
    
    
}
  
}
















 
 
  