import sequtils,strutils,math
type
    idou = tuple[to : int, cost : int]
var
    N = stdin.readline.parseInt
    S = newSeq[int](0)
    bound = newSeqWith(N,newSeq[idou](0))
    flag = newSeqWith(N,0)
    A,B,C : int
    scost = 0
    ans = high(int)
    miti : seq[int]
for n in 0..<N:
    S.add(stdin.readline.parseInt)
var M = stdin.readline.parseInt
for m in 0..<M:
    (A,B,C) = stdin.readline.split.map(parseInt)
    bound[A].add((B,C))
    bound[B].add((A,C))
    
miti = @[0]

proc tansaku(a : int)=
    if a == N - 1 and miti.len > 3:
        var m1,m2 : int
        var sflag = newSeqWith(N,false)
        for m in miti:
            if m == 0 or m == N - 1 or sflag[m] == true:
                continue
            if m1 == 0:
                m1 = S[m]
            elif m2 == 0:
                m2 = S[m]
                (m1,m2) = (min(m1,m2),max(m1,m2))
            elif m2 > S[m]:
                m2 = S[m]
                (m1,m2) = (min(m1,m2),max(m1,m2))
            sflag[m] = true
        if m1 != 0 and m2 != 0:
            ans = min(ans,scost + m1 + m2)
    else:
        for b in bound[a]:
            if flag[b.to] < 2:
                flag[b.to] += 1
                scost += b.cost
                miti.add(b.to)
                tansaku(b.to)
                discard miti.pop
                flag[b.to] -= 1
                scost -= b.cost

flag[0] = 1
tansaku(0)
echo ans