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.*;
public class Main {
    
    static int w[];
    static int UF[];
    
    public static void main(String[] args) {
        Scanner leer = new Scanner(System.in);
        int n = leer.nextInt();
        int qualific[] = new int[n+1];
        FastUnionWeightedUnion(n+1);
        
        for (int i = 1; i < n+1; i++)
            qualific[i] = leer.nextInt();
        
        int m = leer.nextInt();
        int[][] applications = new int[m][3];
        for (int i = 0; i < m; i++) {
            int a = leer.nextInt();
            int b = leer.nextInt();
            int c = leer.nextInt();
            applications[i] = new int[]{a,b,c};
            union(a, b);
        }
        HashSet<Integer> dif = new HashSet<Integer>();
        for (int i = 1; i < UF.length; i++) 
            dif.add(UF[i]);
        
        boolean hasTree = dif.size()==1;
        
        if(!hasTree)
            System.out.println("-1");
        else{
            solve(n, qualific, m, applications);
        }        
    }
    public static void solve(int n, int[] qualific, int m, int[][] applications){
        Node[] nodes = createNodes(n);
        LinkedList<Edge>[] listAdy = createListAdy(applications, n,nodes);
        Node source = nodes[nodeSource(qualific)];
         
        dijsktra(listAdy, source, nodes);
        
        int sum = 0;
        for (int i = 1; i < nodes.length; i++) {
            int wHijo = nodes[i].totalW;
            int res = wHijo;
            sum+=res;
        }
        int cont = 0;
        for (int i = 1; i < nodes.length; i++) {
            if(nodes[i].p == nodes[i])
                cont++;
        }
        if(cont>1)
            System.out.println(-1);
        else
            System.out.println(sum);
    }
    private static int nodeSource(int[] qualific) {
        int max = 0,maxIdx=1;
        for (int i = 1; i < qualific.length; i++) {
            if(qualific[i]>max){
                max = qualific[i];
                maxIdx=i;
            }
        }
        return maxIdx;
    }
    public static Node[] createNodes(int n){
        Node[] nodes = new Node[n+1];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new Node();        
            nodes[i].val=i;
        }
        return nodes;
    }
    public static LinkedList<Edge>[] createListAdy(int[][] applications, int n,Node[]  nodos){
        LinkedList<Edge>[] listAdy = new LinkedList[n+1];
        for (int i = 0; i < listAdy.length; i++) {
            listAdy[i] = new LinkedList<Edge>();
        }
        for (int i = 0; i < applications.length; i++) {
            int idxA= applications[i][0];
            int idxB = applications[i][1];
            int w = applications[i][2];
            Edge e = new Edge(nodos[idxA],nodos[idxB],w);
            listAdy[idxA].add(e);
        }
        return listAdy;
    }
    
    public static void FastUnionWeightedUnion(int N) {
        UF = new int[N];
        for (int i = 0; i < N; i++) 
            UF[i] = i;
        w = new int[N];
        Arrays.fill(w, 1);
    }
    
    public static void union(int i, int j){
        int a = root(i);
        int b = root(j);
        
        if(a==b)
            return;
        
        if(w[a] > w[b]){
            int tempA = a;
            a = b;
            b = tempA;
        }
        UF[a] = b;
        w[b] += w[a];
    }    
    
    public static int root(int x){
        while(x != UF[x]){
            int uf = UF[x];
            UF[x] = UF[UF[x]];
            x = uf;
        }
        return x;
    }
    
    static final int INF=Integer.MAX_VALUE;
    public static void dijsktra(LinkedList<Edge>[] listAdy, Node s, Node[] nodos){        
        for (Node n: nodos) 
            if(n!=s)
                n.totalW=INF;
        
        PriorityQueue<Node> abiertos= new BinaryHeap<>();
        abiertos.add(s);
        
        while(!abiertos.isEmpty()){
            Node actual=abiertos.removeMax();
            for (Edge edge : listAdy[actual.val]) {
                Node destino=edge.b;
                int newW=edge.w;
                relax(actual,destino,newW,abiertos);
            }
        }
    }
    private static void relax(Node actual,Node destino, int newW, PriorityQueue<Node> abiertos) {
        if(newW<destino.totalW){
            destino.totalW=newW;
            destino.p=actual;
            if(abiertos.contains(destino))
                abiertos.incrementPriority(destino.idx, destino);
            else
                abiertos.add(destino);
        }
    }

    abstract static class PriorityQueue<T extends Comparable> {
        protected ArrayList<T> array;
        public abstract void add(T v);
        public abstract T removeMax();
        public abstract T getMax();
        public abstract void incrementPriority(int idx, T v);
        public abstract boolean isEmpty();
        public abstract boolean contains(T v);
    }
    
    static class Node implements Comparable<Node>{
        public int idx,totalW, val;
        public Node p;
        public Node(){
            p= this;
        }
        @Override
        public int compareTo(Node n) {
            return n.totalW-totalW;
        }
        public void swap(Node n){
            int temp=idx;
            this.idx=n.idx;
            n.idx=temp;
        }
        @Override
        public String toString(){
            return "(idx = "+idx+", val = "+val+" totalW = "+totalW+")";
        }
    }
    
    static class Edge {
        Node a,b;
        int w;
        public Edge(Node a, Node b, int w){
            this.a=a;
            this.b=b;
            this.w=w;
        }
    }   
    
    static class BinaryHeap<T extends Node> extends PriorityQueue<T>{
        public BinaryHeap(){
            array= new ArrayList<>();
            array.add(null);
        }
    
        private void swap(int idxHijo, int idxPadre) {
            T temp=array.get(idxHijo);
            array.set(idxHijo,array.get(idxPadre));
            array.set(idxPadre,temp);
            array.get(idxHijo).swap(array.get(idxPadre));
        }
        private void sink(int idxPadre){
            int idxHijoI=idxPadre*2;
            int idxHijoD=idxPadre*2+1;
            while(idxHijoI<array.size()){
                int idxComparacion=idxHijoI;
                if(idxHijoD<array.size() && 
                        array.get(idxHijoI).compareTo(array.get(idxHijoD))<0)
                    idxComparacion=idxHijoD;
                if(array.get(idxPadre).compareTo(array.get(idxComparacion))<0)
                    swap(idxPadre, idxComparacion);

                idxPadre=idxComparacion;
                idxHijoI=idxPadre*2;
                idxHijoD=idxPadre*2+1;
            }

        }
        private void swim(int idxHijo){
            int idxPadre=idxHijo/2;
            while(idxPadre>0){
                if(array.get(idxHijo).compareTo(array.get(idxPadre))>0)
                    swap(idxHijo,idxPadre);
                idxHijo=idxPadre;
                idxPadre=idxHijo/2;
            }

        }
        @Override
        public void add(T v) {
            v.idx = array.size();
            array.add(v);
            swim(array.size()-1);
        }

        @Override
        public T removeMax() {
            if(array.size()>2){
                T max=array.get(1);
                T last=array.remove(array.size()-1);
                max.swap(last);
                array.set(1, last);
                
                sink(1);
                return max;
            }
            else{
                T max=array.remove(1);
                return max;
            }
            
        }
        @Override
        public T getMax() {
            return array.get(1);
        }
        @Override
        public void incrementPriority(int idx, T v) {
            
            array.set(idx, v);
            swim(idx);
        }

        @Override
        public boolean isEmpty(){
            return array.size()==1;
        }

        @Override
        public boolean contains(T v) {
            return array.contains(v);
        }    
    }
}
