import Control.Monad
import Data.Map ((!))
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as B
import Data.Maybe

type Vertex = Int
type Weight = Int
type Edge = ((Vertex, Vertex), (Weight, Path))
type Path = [Vertex]
type Memo = M.Map (Vertex, Vertex) (Weight, Path)

buildG :: [Edge] -> Memo
buildG = M.fromList

readUndirectedEdge :: B.ByteString -> [Edge]
readUndirectedEdge = concatMap ((\[s,t,w] -> [((s,t),(w,[s,t])),((t,s),(w,[t,s]))]) . map readVertex . B.words) . B.lines

readVertex :: B.ByteString -> Vertex
readVertex = fst . fromJust . B.readInt

main :: IO ()
main = do
  n <- readLn
  ss <- replicateM n readLn
  _ <- getLine
  es <- readUndirectedEdge <$> B.getContents
  let g = buildG es
  print (stay2 n ss g)

stay2 :: Int -> [Int] -> Memo -> Int
stay2 n ss = minimum . pay n ss . warshallFloyd n

pay :: Int -> [Int] -> Memo -> [Int]
pay n ss m = do
  s1 <- [1..n-2]
  s2 <- [1..n-2]
  guard (s1 /= s2)
  return (cost m 0 s1 + cost m s1 s2 + cost m s2 (n-1) + ss!!s1 + ss!!s2)

cost m s t = fst (m!(s,t)) 

warshallFloyd :: Int -> Memo -> Memo
warshallFloyd n m = foldl short m [(k,i,j) | k<-[0..n-1], i<-[0..n-1], j<-[0..n-1]]

short m (k,i,j) = M.insertWith lexmin (i,j) (connect m k i j) m

connect m k i j = maybe (100000,[]) id $ do
  (w1,p1) <- M.lookup (i,k) m
  (w2,p2) <- M.lookup (k,j) m
  return (w1 + w2, init p1 ++ tail p2)

lexmin (w1,p1) (w2,p2)
  | w1 < w2 = (w1, p1)
  | w1 == w2 = (w1, min p1 p2)
  | otherwise = (w2,p2)