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.
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-10;
const double PI = acos(-1.0);
template <class T>
T gcd(T a, T b) {
  for (T c; b; c = a, a = b, b = c % b)
    ;
  return a;
}
template <class T>
void out(const vector<T> &a) {
  for (int i = 0; i < ((int)(a).size()); ++i) cout << a[i] << " ";
  cout << endl;
}
int countbit(int n) { return n == 0 ? 0 : 1 + countbit(n & (n - 1)); }
const int d8[8][2] = {{1, 0}, {-1, 0},  {0, 1},  {0, -1},
                      {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
const int d4[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
inline int dcmp(double x) { return (x > EPS) - (x < -EPS); }
inline double cross(const complex<double> &a, const complex<double> &b) {
  return (conj(a) * b).imag();
}
inline double dot(const complex<double> &a, const complex<double> &b) {
  return (conj(a) * b).real();
}
struct edge {
  int v, c, f, w, dual;
  edge(int _v, int _c, int _w, int _dual) : v(_v), c(_c), w(_w), dual(_dual) {
    f = 0;
  }
};
const int N = 1000 * 2 + 10;
vector<edge> g[N];
vector<edge>::iterator ind[N];
int d[N], dp[N], pre[N], q[N];
bool flag[N];
int v[N];
const int INF = 1000000000;
void add_edge(int x, int y, int c, int z) {
  g[x].push_back(edge(y, c, z, ((int)(g[y]).size())));
  g[y].push_back(edge(x, 0, -z, ((int)(g[x]).size()) - 1));
}
int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", v + i);
  scanf("%d", &m);
  int s = n * 2, t = s + 1;
  while (m--) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    --x;
    --y;
    add_edge(x, y + n, 1, z);
  }
  for (int i = 0; i < n; ++i) add_edge(s, i, n, 0);
  for (int i = 0; i < n; ++i) add_edge(i + n, t, 1, 0);
  int cost = 0;
  n = n * 2 + 2;
  while (true) {
    int i;
    pre[s] = pre[t] = -1;
    fill(d, d + n, INF);
    d[s] = 0;
    dp[s] = INF;
    int head, tail;
    head = tail = 0;
    q[tail++] = s;
    memset(flag, 0, sizeof(flag));
    flag[s] = true;
    while (head != tail) {
      i = q[head];
      flag[i] = false;
      for (vector<edge>::iterator it = g[i].begin(); it != g[i].end(); ++it)
        if (it->c > it->f && d[it->v] > d[i] + it->w) {
          d[it->v] = d[i] + it->w;
          pre[it->v] = i;
          ind[it->v] = it;
          dp[it->v] = min(dp[i], it->c - it->f);
          if (!flag[it->v]) {
            flag[it->v] = true;
            q[tail++] = it->v;
            if (tail == n) tail = 0;
          }
        }
      ++head;
      if (head == n) head = 0;
    }
    if (pre[t] < 0) break;
    int aug = dp[t];
    for (i = t; pre[i] != -1; i = pre[i]) {
      ind[i]->f += aug;
      g[ind[i]->v][ind[i]->dual].f -= aug;
      cost += aug * ind[i]->w;
    }
  }
  int cnt = 0;
  for (int i = 0; i < ((int)(g[s]).size()); ++i) cnt += g[s][i].f;
  n = (n - 2) / 2;
  if (cnt == n - 1)
    printf("%d\n", cost);
  else
    puts("-1");
  return 0;
}
