import heapq

def main():
    n = int(input())
    s = [int(input()) for _ in range(n)]
    m = int(input())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        adj[a].append((b, c))
        adj[b].append((a, c))
    
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        heap = [(0, i)]
        while heap:
            cost, u = heapq.heappop(heap)
            if cost > dist[i][u]:
                continue
            for v, c in adj[u]:
                if dist[i][v] > dist[i][u] + c:
                    dist[i][v] = dist[i][u] + c
                    heapq.heappush(heap, (dist[i][v], v))
    
    min_total = INF
    destination = n - 1
    for u in range(1, destination):
        for v in range(1, destination):
            if u == v:
                continue
            su = s[u]
            sv = s[v]
            cost1 = dist[0][u] + dist[u][v] + dist[v][destination]
            valid1 = cost1 < INF
            cost1 = cost1 + su + sv if valid1 else INF
            
            cost2 = dist[0][v] + dist[v][u] + dist[u][destination]
            valid2 = cost2 < INF
            cost2 = cost2 + su + sv if valid2 else INF
            
            current_min = min(cost1, cost2)
            if current_min < min_total:
                min_total = current_min
    print(min_total)

if __name__ == '__main__':
    main()