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 static java.util.Arrays.*;
import static java.lang.Math.*;
import java.util.*;
import java.io.*;

public class B implements Runnable
{
    public static void main(String [] args) throws IOException
    {
        new Thread(null, new B(), "", 1 << 20).start();
    }
    
    String file = "input";
    BufferedReader input;
    PrintWriter out;
    
    public void run() 
    {
        try
        {
            //input = new BufferedReader(new FileReader(file + ".in"));
            input = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(new BufferedOutputStream(System.out));
            solve();
            input.close();
            out.close();
        }
        catch(Exception e)
        {
            e.printStackTrace();
            System.exit(1);
        }
    }
    int[] p;
    int[] q;
    int[][] cost;
    int INF = 1 << 25;
    void solve() throws IOException
    {
        int n = nextInt();
        p = new int[n + 1];
        q = new int[n + 1];
        cost = new int[n + 1][n + 1];
        StringTokenizer st = tokens();
        for(int i = 1; i <= n; i++) q[i] = nextInt(st);
        for(int[] t : cost) fill(t, -1);
        fill(p, -1);
        int m = nextInt();
        for(int i = 0; i < m; i++)
        {
            st = tokens();
            int u = nextInt(st), v = nextInt(st), c = nextInt(st);
            if(cost[u][v] == -1) cost[u][v] = c;
            cost[u][v] = min(cost[u][v], c);
        }
        int res = 0, count = 0;
        for(int i = 1; i <= n; i++)
        {
            int min = INF, id = -1;
            for(int j = 1; j <= n; j++)
                if(cost[j][i] >= 0 && cost[j][i] < min)
                {
                    min = cost[j][i];
                    id = j;
                    
                }
            p[i] = id;
            if(p[i] != -1) 
            {
                res += min;
                count++;
            }
        }
        if(count == n - 1) System.out.println(res);
        else System.out.println(-1);
    }

    StringTokenizer tokens() throws IOException
    {
        return new StringTokenizer(input.readLine());
    }
    
    String next(StringTokenizer st)
    {
        return st.nextToken();
    }
    
    int nextInt() throws IOException
    {
        return Integer.parseInt(input.readLine());
    }
    
    int nextInt(StringTokenizer st)
    {
        return Integer.parseInt(st.nextToken());
    }
    
    double nextDouble() throws IOException
    {
        return Double.parseDouble(input.readLine());
    }
    
    double nextDouble(StringTokenizer st)
    {
        return Double.parseDouble(st.nextToken());
    }
    
    void print(Object... o)
    {
        out.println(deepToString(o));
    }
}