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 Main {


    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int n = nextInt();
        int q[] = new int[n];
        int f = 0;
        for (int i = 0; i < n; i++) {
            q[i] = nextInt();
            if (q[f] < q[i]) f = i;
        }
        int m = nextInt();
        TreeMap<Integer, Integer>[] a = new TreeMap[n];
        for (int i = 0; i < n; a[i] = new TreeMap<>(), i++) ;
        for (int i = 0; i < m; i++) {
            int from = nextInt() - 1;
            int to = nextInt() - 1;
            if (!a[from].containsKey(to)) a[from].put(to, nextInt());
            else a[from].put(to, Math.min(nextInt(), a[from].get(to)));
        }
        long d[] = new long[n];
        Arrays.fill(d, Long.MAX_VALUE / 2);
        d[f] = 0;
        int p[] = new int[n];
        p[f] = f;
        TreeSet<point> ts = new TreeSet<>((o1, o2) -> Long.compare(o1.dist, o2.dist) * 2 + Integer.compare(o1.v, o2.v));
        ts.add(new point(f, 0));
        while (!ts.isEmpty()) {
            point x = ts.pollFirst();
            for (Map.Entry<Integer, Integer> v : a[x.v].entrySet()) {
                int key = v.getKey();
                int value = v.getValue();
                if (d[key] > value) {
                    ts.remove(new point(key, d[key]));
                    d[key] = value;
                    p[key] = x.v;
                    ts.add(new point(key, d[key]));
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (d[i] == Long.MAX_VALUE / 2) {
                System.out.println(-1);
                return;
            }
        }
        TreeSet<Integer> check = new TreeSet<>();
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int x = i;
            while (x != f) {
                if (!check.contains(x)) {
                    ans += a[p[x]].get(x);     // edge btw x && p[x]
                    check.add(x);
                }
                x = p[x];
            }
        }
        out.println(ans);
        out.close();
    }

    static BufferedReader br;
    static StringTokenizer st = new StringTokenizer("");

    static String next() throws IOException {
        while (!st.hasMoreTokens() || st == null) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
}

class point {
    int v;
    long dist;

    public point(int v, long dist) {
        this.v = v;
        this.dist = dist;
    }
}