module WeightedDirectedGraph
  (* 辺の重み *)
  (Weight : sig
    type t
    val zero : t
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  (* ハッシュテーブルを使うようにしたダイクストラ法の実装 *)
  val raw_dijkstra :
    (* 頂点数（Hashtblを用いるので目安程度） *)
    int ->
    (* 隣接リスト *)
    ('v -> ('v * Weight.t) list) ->
    (* 始点 *)
    'v ->
    (* 始点から辿り着けなければNoneを返す関数 *)
    ('v -> Weight.t option)
end =
struct
  module WMap = Map.Make (Weight)

  let raw_dijkstra n es s =
    let d = Hashtbl.create n in
    Hashtbl.add d s Weight.zero;
    let rec dijkstra_aux q =
      match WMap.min_binding_opt q with
      | None -> ()
      | Some (w, us) ->
          dijkstra_aux @@
          Fun.flip (Fun.flip List.fold_left (WMap.remove w q)) us @@ fun q u ->
            if 0 < Weight.compare w (Hashtbl.find d u)
            then q
            else Fun.flip (Fun.flip List.fold_left q) (es u) @@ fun q (v, c) ->
              let open Weight in
              match Hashtbl.find_opt d v with
              | Some d when Weight.compare d (w + c) <= 0 -> q
              | _ ->
                  Hashtbl.replace d v (w + c);
                  WMap.add (w + c) (v :: try WMap.find (w + c) q with Not_found -> []) q in
    dijkstra_aux (WMap.singleton Weight.zero [s]);
    Hashtbl.find_opt d
end

module G = WeightedDirectedGraph (struct
  type t = int
  let zero = 0
  let ( + ) = ( + )
  let compare = compare
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 d = Fun.flip (G.raw_dijkstra (n * 2501)) (0, min 2500 s) @@ fun (v, w) ->
    (let (c, d) = vs.(v) in ((v, min 2500 (w + c)), d)) ::
      Fun.flip List.filter_map es.(v) (fun (u, a, b) ->
        if w < a
        then None
        else Some ((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 -> Option.value ~default:max_int @@ d (v, w)
  done
