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.util.regex.*;
import java.text.*;
import java.math.*;
public class Main
{
    Scanner cin;
    long []q;
    int N;
    int M;
    int []u;
    int []v;
    long []c;
    boolean []visited;
    class node implements Comparable
    {
    	int idx;
    	long v;
    	node (int i,int j)
    	{
    		idx=i;
    		v=j;
    	}
    	public int compareTo(Object oo)
    	{
    		node o=(node)oo;
    		if(v>o.v) return -1;
    		if(v<o.v)return 1;
    		return 0;
    	}
    }
    node []a;
    void work()
    {
    	cin=new Scanner(System.in); 
        N=cin.nextInt();
        a=new node[N];
        for(int i=0;i<N;i++)
        {
        	int tmp=cin.nextInt();
        	a[i]=new node(i,tmp);
        }
        Arrays.sort(a);
        M=cin.nextInt();
        u=new int[M];
        v=new int[M];
        c=new long[M];
        for(int i=0;i<M;i++)
        {
        	u[i]=cin.nextInt();
        	v[i]=cin.nextInt();
        	c[i]=cin.nextInt();
        	u[i]--;v[i]--;
        }
        visited=new boolean[N];
        visited[a[0].idx]=true;
        long ret=0;
        for(int i=1;i<a.length;i++)
        {
        	int now=a[i].idx;
        	long minv=100000000;
        	for(int j=0;j<M;j++)
        	{
        		if(v[j]==now&&visited[u[j]])
        		{
        			minv=Math.min(minv, c[j]);
        		}
        	}
        	if(minv==100000000) 
        	{
        		ret=-1;
        		break;
        	}
        	ret+=minv;
        	visited[now]=true;
        }
        System.out.println(ret);
    }
   
  public static void main(String args[]) throws Exception 
  { 
   
   new Main().work();
  } 


}  

