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.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;


public class R017B {
    public void debug(Object... objects) { System.err.println(Arrays.deepToString(objects)); }
    public static final int INF = 987654321;
    public static final long LINF = 987654321987654321L;
    public static final double EPS = 1e-9;
    
    class Edge implements Comparable<Edge>{ 
        int u, v, cost;
        Edge(int u, int v, int cost) { this.u = u; this.v = v; this.cost = cost; }
        public int compareTo(Edge that) { return this.cost - that.cost; }
        public String toString() { return "(" + u + ":" + v + " " + cost + ")"; }
    }
    // n要素で初期化
    void init(int V) { for(int i=0; i<V; i++) { par[i] = i; } }
    // 木の根を求める
    int find(int x) { if(par[x] == x) { return x; } else { return par[x] = find(par[x]); } }
    // xとyの属する集合を併合
    void unite(int x, int y) { x = find(x); y = find(y); if(x == y) { return; } if(rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if(rank[x] == rank[y]) { rank[x]++; } } }
    // xとyが同じ集合に属するか否か
    boolean same(int x, int y) { return find(x) == find(y); }
    
    int n;
    int[] q;
    int m;
    List<Edge> es;
    int[] par;	// 親
    int[] rank;	// 木の深さ
    boolean[] flag;
    
    public R017B() {
        Scanner scanner = new Scanner(System.in);
        this.n = scanner.nextInt();
        this.q = new int[n];
        for(int i=0; i<n; i++) {
            q[i] = scanner.nextInt();
        }
        this.m = scanner.nextInt();
        this.es = new ArrayList<Edge>();
        for(int i=0; i<m; i++) {
            int a = scanner.nextInt() - 1;
            int b = scanner.nextInt() - 1;
            int c = scanner.nextInt();
            es.add(new Edge(a, b, c));
        }
        this.par = new int[n];
        this.rank = new int[n];
        this.flag = new boolean[n];
    }
    
    int improvedKruskal() {
        Collections.sort(es);
        init(n);
        int res = 0;
        int cnt = 0;
        for(int i=0; i<m; i++) {
            Edge e = es.get(i);
            if(!same(e.u, e.v) && q[e.u] > q[e.v] && !flag[e.v]) {
                cnt++;
                unite(e.u, e.v);
                res += e.cost;
                flag[e.v] = true;
            }
        }
        if(cnt != n-1)  { return -1; }
        return res;
    }
    
    private void solve() {
        System.out.println(improvedKruskal());
    }
    
    public static void main(String[] args) { new R017B().solve(); }
}
