import System.IO
import Data.Char (isSpace)

data Edge = Edge { to :: Int, cost :: Int, time :: Int } deriving Show
data State = State { node :: Int, usedCost :: Int, totalTime :: Int } deriving Show

shortestPath :: Int -> Int -> [[Edge]] -> Int
shortestPath n c graph =
    let maxVal = 1000000000 -- Simulating INT_MAX
        dp = [[maxVal | _ <- [0..c]] | _ <- [0..n-1]]
        dp' = updateDP dp [(0, 0, 0)] -- Start with node 0, cost 0, time 0
        updateDP d [] = d
        updateDP d ((currNode, currCost, currTime):rest) =
            let d' = if currTime < d !! currNode !! currCost then replace2D currNode currCost currTime d else d
                neighbors = [(to e, currCost + cost e, currTime + time e) | e <- graph !! currNode, currCost + cost e <= c]
                newStates = filter (\(n, c, t) -> t < d !! n !! c) neighbors
            in updateDP d' (rest ++ newStates)
        ans = minimum [dp' !! (n-1) !! i | i <- [0..c]]
    in if ans == maxVal then -1 else ans

replace2D :: Int -> Int -> Int -> [[Int]] -> [[Int]]
replace2D x y newVal matrix =
    take x matrix ++ [take y (matrix !! x) ++ [newVal] ++ drop (y + 1) (matrix !! x)] ++ drop (x + 1) matrix

parseInput :: IO ([[Edge]], Int, Int, Int)
parseInput = do
    [n, c, v] <- fmap (map read . words) getLine
    edges <- sequence [fmap (map read . words) getLine | _ <- [1..v]]
    let edgesProcessed = [(s-1, t-1, y, m) | [s, t, y, m] <- edges] -- Convert to zero-based indexing
    let graph = [[Edge t' y m | (s', t', y, m) <- edgesProcessed, s' == i] | i <- [0..n]]
    return (graph, n, c, v)

main :: IO ()
main = do
    (graph, n, c, _) <- parseInput
    print $ shortestPath n c graph