import Control.Monad
import Data.Function
import Data.List
import qualified Data.Map as M
import qualified Data.Set as S
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U

solve n m s lines exchanges = ans where
  ans =
    map (minimum . map snd)
    . tail
    . groupBy ((==) `on` fst)
    . ((1,0):)
    . map (\((v, _), (t, _)) -> (v, t))
    . M.toAscList
    $ dijkstra suc (1, min 2450 s)
  suc (u, s) = ex ++ [((v,s-a), b) | (v,a,b) <- adj V.! (u-1), s>=a] where
    ex = [((u, s+c), d) | s+c <= 2450]
    (c,d) = U.fromListN n exchanges U.! (u-1)
  adj =
    V.fromList . map snd . M.toAscList
    $ foldr addL (M.fromList . zip [1..n] $ repeat []) lines
  addL (u,v,a,b) = M.adjust ((v,a,b):) u . M.adjust ((u,a,b):) v

main = do
  [n, m, s] <- readWords
  lines <- replicateM m $ (\[a,b,c,d]->(a,b,c,d)) <$> readWords
  exchanges <- replicateM n $ (\[a,b]->(a,b)) <$> readWords
  mapM_ print $ solve n m s lines exchanges

readWords = map read . words <$> getLine

dijkstra suc st = M.delete st res where
  res = go (M.singleton st (0, st), S.singleton (0, st))
  go (res, que)
    | S.null que = res
    | otherwise = go $ foldl' f (res, S.deleteMin que) (suc u)
    where
      (du, u) = S.findMin que
      f (res, que) (v, cost)
        | v `M.member` res && fst (res M.! v) <= alt = (res, que)
        | otherwise = (M.insert v (alt, u) res, S.insert (alt, v) que)
        where alt = du + cost