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>
int bin1(long long int x) {
  int r = 0;
  while (x) {
    r++;
    x &= x - 1;
  }
  return r;
}
long long int exgcd(long long int a, long long int b, long long int &x,
                    long long int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long int x1, y1, __gcd = exgcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return __gcd;
}
long long int modpow(long long int b, long long int e, long long int m) {
  long long int r = 1;
  b = b % m;
  while (e > 0) {
    if (e % 2 == 1) r = (r * b) % m;
    e /= 2;
    b = (b * b) % m;
  }
  return r;
}
long long int modinverse(long long int a, long long int mod) {
  return modpow(a, mod - 2, mod);
}
long long int modinverse2(long long int a, long long int m) {
  long long int x, y;
  exgcd(a, m, x, y);
  while (x < 0) x += m;
  return x;
}
long long int nCrmod(long long int n, long long int r, long long int m) {
  if (r > n) r = n - r;
  long long int res = 1;
  for (long long int i = r; i >= 1; i--) {
    res = (res * (n - i + 1)) % m;
    res = (res * modinverse(i, m));
  }
  return res;
}
long long int power(long long int b, long long int e) {
  if (e == 0) return 1;
  if (e % 2 == 0) return power(b * b, e / 2);
  return b * power(b * b, e / 2);
}
double powerf(double b, int e) {
  if (e == 0) return 1;
  if (e % 2 == 0)
    return powerf(b * b, e / 2);
  else {
    if (e > 0)
      return b * powerf(b * b, e / 2);
    else
      return powerf(b * b, e / 2) / b;
  }
}
long long int totient(long long int n) {
  long long int res = n, p;
  for (p = 2; p * p <= n; p++) {
    if (n % p == 0) {
      while (n % p == 0) n /= p;
      res -= res / p;
    }
  }
  if (n > 1) res -= res / n;
  return res;
}
bool isprime(long long int x) {
  if (x == 1) return false;
  for (long long int i = 2; i * i <= x; i++)
    if (x % i == 0) return false;
  return true;
}
bool prime[1010 + 1];
void sieve() {
  long long int x, y;
  prime[0] = prime[1] = true;
  for (x = 2; x * x <= 1010; x++) {
    if (!prime[x])
      for (y = x * x; y <= 1010; y += x) prime[y] = true;
  }
}
long long int lpf(long long int x) {
  while (x % 2 == 0) x /= 2;
  if (x < 2) return 2;
  long long int i = 3;
  while (x > i) {
    if (x % i)
      i += 2;
    else
      while (x % i == 0) x /= i;
  }
  return i;
}
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
using namespace std;
void gcj() {
  long long int t;
  cin >> t;
  for (long long int c = 1; c <= t; c++) {
    cout << "Case #" << c << ": ";
    cout << endl;
  }
}
void judge() {
  long long int n, m, q, a, b, c, ans = 0;
  cin >> n;
  for (long long int i = 0; i < n; i++) cin >> q;
  vector<long long int> parent(n, 0);
  vector<long long int> cost(n, INT_MAX);
  cin >> m;
  while (m--) {
    cin >> a >> b >> c;
    if (parent[b - 1] == 0) parent[b - 1] = 1;
    cost[b - 1] = min(cost[b - 1], c);
  }
  if (count(parent.begin(), parent.end(), 0) != 1) {
    cout << -1;
    return;
  }
  for (long long int i = 0; i < n; i++)
    if (parent[i]) ans += cost[i];
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long int t = 1;
  while (t--) {
    judge();
  }
  return 0;
}
