import Control.Monad
import Control.Monad.ST
import qualified Data.ByteString.Char8 as C
import Data.List
import Data.Vector.Unboxed ((!), Vector, freeze)
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM

main = C.interact $ put . sol . get

get = U.unfoldr (C.readInt . C.dropWhile (<'0'))

put = C.pack . show

sol v = minimum . fmap plen . permutations $ U.toList rs
  where
  (n,m,r) = (v!0,v!1,v!2)
  (rs,es) = U.splitAt r (U.drop 3 v)
  tbl = wf n m es
  getw i j = tbl!(i*(n+1)+j)
  plen p = sum $ zipWith getw p (tail p)

wf n m es = runST $ do
  tbl <- UM.replicate ((n+1)^2) (10^5)
  let
    ix i j = i*(n+1)+j
    putw i j w = UM.unsafeWrite tbl (ix i j) w
    getw i j = UM.unsafeRead tbl (ix i j)
  forM_ [0..m-1] $ \e -> do
    let (i,j,w) = (es!(3*e),es!(3*e+1),es!(3*e+2))
    putw i j w
    putw j i w
  forM_ [1..n] $ \k ->
    forM_ [1..n] $ \i ->
      forM_ [1..n] $ \j -> do
        a <- getw i k
        b <- getw k j
        p <- getw i j
        putw i j (min p (a+b))
  freeze tbl