module IntMap = Map.Make (struct
  type t = int
  let compare = compare
end)

let () = Scanf.scanf "%d %d %d\n" @@ fun n m s ->
  let es = Array.make_matrix n 2501 [] in
  for i = 0 to m - 1 do
    Scanf.scanf "%d %d %d %d\n" @@ fun u v a b ->
      for i = a to 2500 do
        es.(u - 1).(i) <- ((v - 1, i - a), b) :: es.(u - 1).(i);
        es.(v - 1).(i) <- ((u - 1, i - a), b) :: es.(v - 1).(i);
      done
  done;
  for v = 0 to n - 1 do
    Scanf.scanf "%d %d\n" @@ fun c d ->
      for j = 0 to 2500 do
        es.(v).(j) <- ((v, min 2500 (j + c)), d) :: es.(v).(j)
      done
  done;
  let d = Array.make_matrix n 2501 1234567890123 in
  d.(0).(min 2500 s) <- 0;
  let rec dijkstra q =
    match IntMap.min_binding q with
    | exception Not_found -> ()
    | (w, us) ->
        dijkstra @@ List.fold_left (fun q (u, u') ->
          if d.(u).(u') < w
          then q
          else List.fold_left (fun q ((v, v'), c) ->
            if compare d.(v).(v') (w + c) <= 0
            then q
            else begin
              d.(v).(v') <- w + c;
              IntMap.add (w + c) ((v, v') :: try IntMap.find (w + c) q with Not_found -> []) q
  end) q es.(u).(u')) (IntMap.remove w q) us in
  dijkstra (IntMap.singleton 0 [(0, min 2500 s)]);
  for i = 1 to n - 1 do
    Printf.printf "%d\n" @@ Array.fold_left min max_int d.(i)
  done

