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.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Hirearchy {

	static  class DisjointSet {
		
		public int[]set; 
		public DisjointSet(int n){
			set=new int[n];
			for (int i = 0; i < set.length; i++) {
				set[i]=i;
			}
		}
		public int find(int x){
			if(set[x]==x)return x;
			return set[x]=find(set[x]);
		}
		public void union(int x,int y){
			set[find(x)]=find(y);
		}

		public int countDSets() {
			int c=0;
			for(int i=0;i<set.length;i++)
				if(set[i]==i)
					c++;
			return c;
		}

	}

	static class Edge implements Comparable<Edge>{
		int from,to,cost;
public Edge(int ff,int tt,int cc){
	from=ff;
	to=tt;
	cost=cc;
}
		@Override
		public int compareTo(Edge o) {
			return cost-o.cost;
		}
		
	}
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		String s = r.readLine();
		int n = new Integer(s);
		s = r.readLine();
		s = r.readLine();
		int m = new Integer(s);
		PriorityQueue<Edge> pq=new PriorityQueue<Edge>();
		while (m-- > 0) {
			s = r.readLine();
			String[] sp = s.split(" ");
			int from = new Integer(sp[0]) - 1;
			int to = new Integer(sp[1]) - 1;
			int cost = new Integer(sp[2]) ;
			pq.add(new Edge(from,to,cost));
		}
		DisjointSet ds=new DisjointSet(n);
		boolean[] in =new boolean[n];
		int cost=0;
		while(!pq.isEmpty()){
			Edge front=pq.remove();
			if(ds.find(front.from)!=ds.find(front.to)&&!in[front.to]){
				in[front.to]=true;
				ds.union(front.from, front.to);
				cost+=front.cost;
			}
		}
		if(ds.countDSets()!=1)System.out.println(-1);else
		System.out.println(cost);
	}
}
