import Data.List
import qualified Data.Vector as V
import Data.Bits

cover n keys =
    case coverMemo n keys V.! 0 of
      Nothing -> -1
      Just x -> x

coverMemo :: Int -> [[Int]] -> V.Vector (Maybe Integer)
coverMemo n [] = V.snoc (V.fromList [Nothing | i <- [0..2^n-2]]) (Just 0)
coverMemo n ([a,b]:cs:rest) =
    let memo = coverMemo n rest in
    let mask = listToInt cs in
    V.fromList [maybeMin (memo V.! i) (maybePlus (fromIntegral a) (memo V.! (mask .|. i)))
               | i <- [0..2^n-1]]

listToInt :: [Int] -> Int
listToInt = foldl (\a -> \x -> a+2^(x-1)) 0

maybeMin :: Maybe Integer -> Maybe Integer -> Maybe Integer
maybeMin Nothing Nothing = Nothing
maybeMin Nothing y = y
maybeMin x Nothing = x
maybeMin (Just x) (Just y) = Just (min x y)

maybePlus :: Integer -> Maybe Integer -> Maybe Integer
maybePlus _ Nothing = Nothing
maybePlus a (Just x) = Just (a+x)

main = do
  n:m:_ <- map read . words <$> getLine :: IO [Int]
  abc <- map (map read . words) <$> lines <$> getContents :: IO [[Int]]
  putStrLn $ show $ cover n abc
