import Control.Monad
import qualified Data.Map as M
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)

readUndirectedEdge :: B.ByteString -> [Edge]
readUndirectedEdge = concatMap (constructEdge . map readInt . B.words) . B.lines

constructEdge :: [Int] -> [Edge]
constructEdge [s,t,w] = [((s,t), (w,[s,t])), ((t,s), (w,[t,s]))]
constructEdge _ = undefined

readInt :: B.ByteString -> Int
readInt = fst . fromJust . B.readInt

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

stay2 :: Int -> [Int] -> [Edge] -> 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 :: Memo -> Vertex -> Vertex -> Weight
cost m s t = fst $ M.findWithDefault (100000,[]) (s,t) m 

warshallFloyd :: Int -> [Edge] -> Memo
warshallFloyd n es = foldl shorten m0 kij
  where
    m0 = M.fromList es
    kij = [(k,i,j) | k<-[0..n-1], i<-[0..n-1], j<-[0..n-1]]

shorten :: Memo -> (Vertex, Vertex, Vertex) -> Memo
shorten m (k,i,j) = case connect m k i j of
  Nothing -> m
  Just (w,p) -> M.insertWith lexmin (i,j) (w,p) m

connect :: Memo -> Vertex -> Vertex -> Vertex -> Maybe (Weight, Path)
connect m k i j = do
  (w1,p1) <- M.lookup (i,k) m
  (w2,p2) <- M.lookup (k,j) m
  return (w1 + w2, init p1 ++ tail p2)

lexmin :: (Weight, Path) -> (Weight, Path) -> (Weight, Path)
lexmin (w1,p1) (w2,p2)
  | w1 < w2 = (w1, p1)
  | w1 == w2 = (w1, min p1 p2)
  | otherwise = (w2,p2)