import Control.Monad
import Data.Map ((!))
import qualified Data.Map as M

main = do
 n <- readLn
 ss <- replicateM n readLn :: IO [Int]
 m <- readLn
 abcs <- map (map read . words) <$> replicateM m getLine
 print (stay2 n ss abcs)

stay2 n ss abcs = minimum ((fullSearch n ss) (warshallFloyd n abcs))

fullSearch n ss g = do
 s1 <- [1..n-2]
 s2 <- [1..n-2]
 guard (s1 /= s2)
 return (g!(0,s1) + g!(s1,s2) + g!(s2,n-1) + ss!!s1 + ss!!s2)

warshallFloyd n abcs = foldl wf g0 [(k,i,j) | k<-[0..n-1], i<-[0..n-1], j<-[0..n-1]]
 where
  g0 = foldr (\[a,b,c] g -> M.insert (b,a) c (M.insert (a,b) c g)) M.empty abcs
  wf g (k,i,j) = M.insertWith min (i,j) v g
   where v = maybe 1000 id ((+) <$> (M.lookup (i,k) g) <*> (M.lookup (k,j) g))