module WeightedDirectedGraph
  (* 辺の重み *)
  (Weight : sig
    type t
    val inf : t (* max_intとかを突っ込むとオーバーフローで死ぬので気をつけること *)
    val zero : t
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  (* 頂点を[0, n)の自然数に限定したグラフに対してのダイクストラ法 *)
  val raw_dijkstra :
    (* 頂点数 *)
    int ->
    (* 隣接リスト *)
    (int -> (int * Weight.t) list) ->
    (* 始点 *)
    int ->
    (* 始点から辿り着けなければWeight.infを返す関数 *)
    (int -> Weight.t)
end =
struct
  module WMap = Map.Make (Weight)

  let raw_dijkstra n es s =
    let d = Array.make n Weight.inf in
    d.(s) <- Weight.zero;
    let rec dijkstra_aux q =
      match WMap.min_binding_opt q with
      | None -> ()
      | Some (w, us) ->
          dijkstra_aux @@
          ListLabels.fold_left ~init:(WMap.remove w q) us ~f:(fun q u ->
            if 0 < Weight.compare w d.(u)
            then q
            else ListLabels.fold_left ~init:q (es u) ~f:(fun q (v, c) ->
              let open Weight in
              if Weight.compare d.(v) (w + c) <= 0
              then q
              else begin
                d.(v) <- w + c;
                WMap.add (w + c) (v :: try WMap.find (w + c) q with Not_found -> []) q
              end)) in
    dijkstra_aux (WMap.singleton Weight.zero [s]);
    Array.get d
end

module G = WeightedDirectedGraph (struct
  type t = int
  let zero = 0
  let ( + ) = ( + )
  let compare = compare
  let inf = 12345678901234
end)

let () = Scanf.scanf "%d %d %d\n" @@ fun n m s ->
  let es = Array.make n [] in
  for i = 0 to m - 1 do
    Scanf.scanf "%d %d %d %d\n" @@ fun u v a b ->
      es.(u - 1) <- (v - 1, a, b) :: es.(u - 1);
      es.(v - 1) <- (u - 1, a, b) :: es.(v - 1);
  done;
  let vs = Array.init n @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun c d -> (c, d) in
  let f (v, w) = n * w + v in
  let finv x = (x mod n, x / n) in
  let d = Fun.flip (G.raw_dijkstra (n * 2501)) (f (0, min 2500 s)) @@ fun p ->
    let (v, w) = finv p in
    (let (c, d) = vs.(v) in (f (v, min 2500 (w + c)), d)) ::
      Fun.flip List.filter_map es.(v) (fun (u, a, b) ->
        if w < a
        then None
        else Some (f (u, w - a), b)) in
  for v = 1 to n - 1 do
    Printf.printf "%d\n" @@
    List.fold_left min max_int @@
    List.init 2501 @@ fun w -> d (f (v, w))
  done
