import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; import java.util.Set; public class Main { public static final int INF = Integer.MAX_VALUE / 2 - 1; public static class Walk implements Comparable { int cost, current, stay1, stay2; public Walk(int cost, int current, int stay1, int stay2) { super(); this.cost = cost; this.current = current; this.stay1 = stay1; this.stay2 = stay2; } @Override public int compareTo(Walk o) { return Integer.compare(this.cost, o.cost); } } public static void main(String[] args){ Scanner sc = new Scanner(System.in); final int N = sc.nextInt(); int[] stay_costs = new int[N]; for(int i = 0; i < N; i++){ stay_costs[i] = sc.nextInt(); } final int M = sc.nextInt(); int[][] adj = new int[N][N]; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ adj[i][j] = INF; } } for(int i = 0; i < M; i++){ final int a = sc.nextInt(); final int b = sc.nextInt(); final int c = sc.nextInt(); adj[a][b] = adj[b][a] = c; } boolean[][][] visited = new boolean[N][N][N]; PriorityQueue queue = new PriorityQueue(); queue.add(new Walk(0, 0, 0, 0)); while(!queue.isEmpty()){ final Walk walk = queue.poll(); if(visited[walk.current][walk.stay1][walk.stay2]){ continue; }else{ visited[walk.current][walk.stay1][walk.stay2] = true; } //System.out.println(walk.current + " " + walk.cost + " " + walk.stay1 + " " + walk.stay2); if(walk.current == N - 1 && walk.stay1 != 0 && walk.stay2 != 0 && walk.stay1 != walk.stay2){ System.out.println(walk.cost); break; } if(walk.current != 0 && walk.current != N - 1){ if(walk.stay1 == 0){ queue.add(new Walk(walk.cost + stay_costs[walk.current], walk.current, walk.current, walk.stay2)); }else if(walk.stay1 != walk.current && walk.stay2 == 0){ queue.add(new Walk(walk.cost + stay_costs[walk.current], walk.current, walk.stay1, walk.current)); } } for(int next = 0; next < N; next++){ if(adj[walk.current][next] >= INF){ continue; }else if(visited[next][walk.stay1][walk.stay2]){ continue; } queue.add(new Walk(walk.cost + adj[walk.current][next], next, walk.stay1, walk.stay2)); } } } }