#include <stdio.h>
#include <stdlib.h>
int min(int **pathcost, int i, int j, int k)
{
  int min;
  if (pathcost[i][j] == -1) {
    if ((pathcost[i][k] == -1) || (pathcost[k][j] == -1)) {
      min = -1;
    } else {
      min = pathcost[i][k] + pathcost[k][j];
    }
  } else {
    if ((pathcost[i][k] == -1) || (pathcost[k][j] == -1)) {
      min = pathcost[i][j];
    } else {
      if (pathcost[i][j] < (pathcost[i][k] + pathcost[k][j])) {
        min = pathcost[i][j];
      } else {
        min = pathcost[i][k] + pathcost[k][j];
      }
    }
  }
  return min;
}
int total(int **pathcost, int *S, int i, int j, int N)
{
  int total;
  if ((pathcost[0][i] == -1)||
      (pathcost[i][j] == -1)||
      (pathcost[j][N-1] == -1)) {
    total = -1;
  } else {
    total = pathcost[0][i] + S[i] 
          + pathcost[i][j] + S[j]
          + pathcost[j][N-1];
  }
  return total;
}
int main()
{
  int N;
  int *S;
  int M;
  int *A;
  int *B;
  int *C;
  scanf("%d", &N);
  S = (int*)malloc(sizeof(int)*N);
  int i;
  for (i=0; i<N; i++) scanf("%d", &(S[i]));
  scanf("%d", &M);
  A = (int*)malloc(sizeof(int)*M);
  B = (int*)malloc(sizeof(int)*M);
  C = (int*)malloc(sizeof(int)*M);
  for (i=0; i<M; i++) {
    scanf("%d", &(A[i]));
    scanf("%d", &(B[i]));
    scanf("%d", &(C[i]));
  }

  int **pathcost;
  pathcost = (int**)malloc(sizeof(int*)*N);
  pathcost[0] = (int*)malloc(sizeof(int)*N*N);
  for (i=0; i<N*N; i++) pathcost[0][i] = -1;
  for (i=1; i<N; i++) pathcost[i] = &(pathcost[i-1][N]);
  for (i=0; i<N; i++) pathcost[i][i] = 0;
  for (i=0; i<M; i++) {
    pathcost[A[i]][B[i]] = C[i];
    pathcost[B[i]][A[i]] = C[i];
  }

  int j, k;
  for (k=0; k<N; k++)
    for (i=0; i<N; i++)
      for (j=0; j<N; j++)
        pathcost[i][j] = min(pathcost, i, j, k);

  int cost;
  int min = ~(1 << 31);
  for (i=1; i<N-1; i++)
    for (j=1; j<N-1; j++) {
      if (i != j) {
        cost = total(pathcost, S, i, j, N);
        if ((cost != -1) && (cost < min)) {
          min = cost;
        }
      }
    }

  printf("%d\n", min);
  return 0;
}