import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] S = new int[N]; for (int i = 0; i < N; i++) { S[i] = scanner.nextInt(); } int M = scanner.nextInt(); final int INF = Integer.MAX_VALUE / 2; int[][] dist = new int[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dist[i][j] = INF; } } for (int i = 0; i < N; i++) { dist[i][i] = 0; } for (int i = 0; i < M; i++) { int A = scanner.nextInt(); int B = scanner.nextInt(); int C = scanner.nextInt(); dist[A][B] = C; dist[B][A] = C; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } int min = INF; for (int i = 1; i < N - 1; i++) { for (int j = 1; j < N - 1; j++) { if (i == j) continue; min = Math.min(min, dist[0][i] + dist[i][j] + dist[j][N - 1] + S[i] + S[j]); } } System.out.println(min); } }