module Main where
import Data.List(permutations,transpose,foldl',foldl1')
import Data.Array
import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)

-- readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

int = fst . fromJust . BC.readInt

main = BC.interact $ printer . solver . parser

wf :: Int -> [[Int]] -> [[Int]]
wf n a = result 
  where    
    nm = n - 1
    wf2 :: Int -> [[Int]] -> [[Int]]
    wf2 k a = res
      where
        ak = a !! k
        atk = map (!!k) a 
        ad x = map (+x) ak
        pl = map ad atk 
        -- res = zipWith (zipWith min) a (map ad atk)
        -- res = zipWith (\x y -> zipWith min x (map (+y) ak)) a atk
        -- res = zipWith (\x y -> zipWith (\u v -> u `min` (v+y)) x ak) a atk
        res = zipWith (res2 $!) a atk
        res2 x y = zipWith (res3 $!) x ak
        res3 u v = u `min` (v+0)
    funcs = map wf2 [0..nm] :: [[[Int]] -> [[Int]]]
    -- result = foldl' (flip id) a funcs
    result = (foldl1' (.) funcs) a

printer :: Int -> BC.ByteString
printer = BC.pack . unlines . (:[]) . show 

parser :: BC.ByteString -> (Int, [Int], [[Int]])
parser input = (n, rms, ll)
  where
    (n:m:r:is1) = map int . BC.words $ input
    (rs,is2) = splitAt r is1
    rms = map (subtract 1) rs
    abcs = map (take 3) $ take m $ iterate (drop 3) is2
    nm = n-1
    arr = array ((0,0),(nm,nm)) ([((i,j),200000) |i<-[0..nm],j<-[0..nm] ] ++ map (\[a,b,c]->((a-1,b-1),c)) abcs)
    ll = [[ arr ! (i,j) | j<-[0..nm] ] | i<-[0..nm]]

distance :: [[Int]] -> [Int] -> Int
distance ll rs = sum $ zipWith (\x y -> (ll !! x) !! y) rs (tail rs)

solver :: (Int, [Int], [[Int]]) -> Int
solver (n, rs, ll) = result 
  where
    ll2 = wf n ll
    result = minimum $ map (distance ll2) $ permutations rs

