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.*;
import java.util.*;

public class HierarchyV {

    private static class mEdge{
        int from;
        int to;
        int weight;

        public mEdge(int f, int t, int w) {
            from = f;
            to = t;
            weight  =w;
        }
    }

    private static class Node{
        int id;
       // int weight;
        int edgeWeight = 0;
        public Node(int i, int w) {
            id = i;
            edgeWeight = w;
        }
    }

    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter printWriter = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
   
    public static void main(String[] args) throws IOException{
    	int n = Integer.parseInt(bufferedReader.readLine());
          String[] inputString = bufferedReader.readLine().trim().split("\\s+");
        int m = Integer.parseInt(bufferedReader.readLine());

//        int n = 5;
//        String[] inputString = {"3","9","2","1","8"};
//        int m = 9;
//        String[] tString = {"2 5 10", "1 3 8", "3 4 9", "5 4 2", "2 1 4","5 1 4","2 4 2","1 4 7","5 1 2"};

  //      int root = 1;
  //  	int highest = 0;
        HashSet<Integer> vertices = new HashSet<Integer>();

        for(int i = 0; i < n; i++) {
            vertices.add(i+1);
//    		int qualification = Integer.parseInt(inputString[i]);
//    		if(qualification > highest){
//    			highest = qualification;
//    			root = i + 1;
//    		}
    	}

        // construct the graph
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
     	for(int i = 0; i < m; i++) {
     		inputString = bufferedReader.readLine().trim().split("\\s+");

     	  //  inputString = tString[i].split("\\s+");
//     			int a = Integer.parseInt(inputString[0]);
     		int b = Integer.parseInt(inputString[1]);
     		int c = Integer.parseInt(inputString[2]);

             if(vertices.contains(b)) {
                vertices.remove(b);
            }

            if(map.containsKey(b)) {
                int val = map.get(b);
                if (val > c) {
                    map.put(b, c);
                } 
            } else {
                map.put(b,c);
            }
        }





     	// 	if(map.containsKey(a)) {
      //           HashMap<Integer,mEdge> tMap = map.get(a);
      //           if(tMap.containsKey(b)) {
      //               mEdge cEdge = tMap.get(b);
      //               if(cEdge.weight > c) {
      //                   cEdge.weight = c;
      //               }
      //           } else {
      //               mEdge cEdge = new mEdge(a,b,c);
      //               tMap.put(b,cEdge);
      //           }
      //       } else {

      //           HashMap<Integer,mEdge> cMap = new HashMap<Integer, mEdge>();
      //           cMap.put(b,new mEdge(a,b,c));
      //           map.put(a,cMap);
      //       }
     	// 	if(vertices.contains(b)) {
      //           vertices.remove(b);
      //       }
     	// }

        if(vertices.size() != 1) {
            printWriter.println(-1);
            printWriter.flush();
            printWriter.close();
        }


        int result = 0;
        for(int i : map.values()) {
            result += i;
        }
       

        printWriter.println(result);
        printWriter.flush();
        printWriter.close();





    }
}
