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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.*;

/**
 * 17B
 *
 * @author artyom
 */
public class Hierarchy implements Runnable {
    private BufferedReader in;
    private PrintStream out;
    private StringTokenizer tok;

    private void solve() throws IOException {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }
        int m = nextInt();
        DiGraph graph = readGraph(n, m, arr);
        out.print(graph.connected() == n ? sum(graph) : -1);
    }

    private long sum(DiGraph graph) {
        long sum = 0;
        for (int w : graph.minIn) {
            if (w != Integer.MAX_VALUE) {
                sum += w;
            }
        }
        return sum;
    }

    private DiGraph readGraph(int n, int m, int[] q) throws IOException {
        DiGraph g = new DiGraph(n);
        for (int i = 0; i < m; i++) {
            int a = nextInt() - 1, b = nextInt() - 1, c = nextInt();
            if (q[a] > q[b]) {
                g.addEdge(b, c);
            }
        }
        return g;
    }

    //--------------------------------------------------------------
    public static void main(String[] args) {
        new Hierarchy().run();
    }

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = System.out;
            tok = null;
            solve();
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    private String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private static final class DiGraph {
        final int[] minIn;

        DiGraph(int nVertices) {
            minIn = new int[nVertices];
            Arrays.fill(minIn, Integer.MAX_VALUE);
        }

        void addEdge(int target, int weight) {
            if (minIn[target] > weight) {
                minIn[target] = weight;
            }
        }

        int connected() {
            int connected = 1;
            for (int w : minIn) {
                if (w != Integer.MAX_VALUE) {
                    connected++;
                }
            }
            return connected;
        }
    }
}