import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)
import Data.List
import Data.Array.IO
import Data.Bits
import Control.Monad

type Memo = IOUArray (Int, Int) Int

main = do
  [n, m, r] <- map read . words <$> getLine :: IO [Int]
  rr <- map read . words <$> getLine :: IO [Int]
  input <- (\[x, y, z] -> zip3 x y z) . transpose <$> getInt2DListBC
  edge <- newArray ((1, 1), (n, n)) (10^5 + 1) :: IO Memo
  pass <- newArray ((1, 1), (n, n)) 0 :: IO Memo
  foldM (memoize pass) edge input
  let index = [(i, j, k) | i <- [1..n], j <- [1..n], k <- [1..n]]
      init = [(i, i, 0) | i <- [1..n]]
      purpose = foldl1 (\x y -> x .|. shift 1 (y - 1)) rr
  foldM memoize' edge init
  foldM (warshallFloyd pass) edge index
  ans <- mapM (readMemo purpose 0 pass edge) $ permutations rr
  putStrLn . show . minimum $ ans

bsToInt :: BC.ByteString -> Int
bsToInt = fst . fromJust . BC.readInt

getInt2DListBC :: IO [[Int]]
getInt2DListBC = map (map bsToInt . BC.words) . BC.lines <$> BC.getContents

memoize :: Memo -> Memo -> (Int, Int, Int) -> IO Memo
memoize pass memo (x, y, d) = do
  writeArray pass (x, y) $ shift 1 (x - 1)
  writeArray pass (y, x) $ shift 1 (y - 1)
  writeArray memo (x, y) d
  writeArray memo (y, x) d
  return memo

memoize' :: Memo -> (Int, Int, Int) -> IO Memo
memoize' memo (x, y, d) = do
  writeArray memo (x, y) d
  return memo

warshallFloyd :: Memo -> Memo -> (Int, Int, Int) -> IO Memo
warshallFloyd pass memo (i, j, k) = do
  p <- readArray pass (i, j)
  x <- readArray memo (i, j)
  y <- readArray memo (i, k)
  z <- readArray memo (k, j)
  let minWeight = min x $ y + z
      pp = if x < y + z then p else p .|. shift 1 (i - 1)
  writeArray memo (i, j) minWeight
  writeArray pass (i, j) pp
  return memo

readMemo :: Int -> Int -> Memo -> Memo -> [Int] -> IO Int
readMemo purpose points pass memo (_:[]) = return 0
readMemo purpose points pass memo (s:t:ts)
  | purpose == purpose .&. points = do
    return 0
  | otherwise = do
    d <- readArray memo (s, t)
    pp <- readArray pass (s, t)
    return =<< (+d) <$> readMemo purpose (points .|. pp) pass memo (t:ts)
