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.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static final int oo = 0x3f3f3f3f;
    private static int[] val;

    public static void main(String[] args) throws IOException {
        InputStream fin = System.in;
        //fin = new FileInputStream("in.txt");
        Scanner cin = new Scanner(fin);

        while (cin.hasNext()) {
            int n = cin.nextInt();
            val = new int[n];
            for (int i = 0; i < n; i++) {
                val[i] = cin.nextInt();
            }
            int m = cin.nextInt();
            Graph g = new Graph(n);
            for (int i = 0; i < m; i++) {
                int u = cin.nextInt() - 1;
                int v = cin.nextInt() - 1;
                int w = cin.nextInt();
                g.add(u, v, w);
            }
            System.out.println(g.get());
        }

        fin.close();
        cin.close();
    }

    static class Graph {
        public int n;

        static class Edge {
            int to, w;
            Edge next;

            Edge(int to, int w) {
                this.to = to;
                this.w = w;
            }
        }

        private int[] q;
        private Edge[] g;
        private int[] d;
        private int[] dp;

        Graph(int n) {
            this.n = n;
            g = new Edge[n];
            d = new int[n];
            dp = new int[n];
            q = new int[n];
            Arrays.fill(g, null);
            Arrays.fill(d, 0);
            Arrays.fill(dp, oo);
        }

        public int get() {
            int root = -1;

            for (int i = 0; i < n; i++) {
                if (d[i] == 0) {
                    if (root != -1) {
                        return -1;
                    } else {
                        root = i;
                    }
                }
            }
            int f, b;

            f = b = 0;
            q[b++] = root;
            while (f != b) {
                int u = q[f++];
                for (Edge it = g[u]; it != null; it = it.next) {
                    int v = it.to;
                    d[v]--;
                    if (d[v] == 0) {
                        q[b++] = v;
                    }
                }
            }

            dp[root] = 0;
            int ret = 0;
            for (int i = 0; i < b; i++) {
                int u = q[i];
                ret += dp[u];
                for (Edge it = g[u]; it != null; it = it.next) {
                    int v = it.to;
                    dp[v] = Math.min(dp[v], it.w);
                }
            }

            return ret;
        }

        public void add(int u, int v, int w) {
            Edge cur = new Edge(v, w);
            cur.next = g[u];
            d[v]++;
            g[u] = cur;
        }
    }
}
