open Core
open Stdio
open Bigarray

let scan_line fo g = Caml.Scanf.sscanf In_channel.(input_line_exn stdin) fo g
let scan_line_1 fo = scan_line fo (fun a -> a)
let scan_line_2 fo = scan_line fo (fun a b -> (a,b))
let scan_line_3 fo = scan_line fo (fun a b c -> (a,b,c))
let scan_line_4 fo = scan_line fo (fun a b c d -> (a,b,c,d))

let money_inf = 50 * 50
let dist_inf = Int64.(10L ** 15L)
type edge_t = { cod : int; unchin : int; jikan : Int64.t }

let n, m, s = scan_line_3 "%d %d %d"
let s = min money_inf s

let edges = Array.create ~len:n []

let () =
    for i = 1 to m do
        let u, v, un, ji = scan_line_4 "%d %d %d %Ld" in
        let u = u - 1 in let v = v - 1 in
        edges.(u) <- { cod = v; unchin = un; jikan = ji } :: edges.(u);
        edges.(v) <- { cod = u; unchin = un; jikan = ji } :: edges.(v)
    done

let maisu_jikan_s =
    Array.init n
    ~f:begin fun _ ->
        let x, y = scan_line_2 "%d %Ld" in
        let x = min x money_inf in
        (x,y)
    end

let res = Array2.create int64 c_layout n (money_inf+1)
let () = Array2.fill res dist_inf

(* cf. https://ocaml.janestreet.com/ocaml-core/latest/doc/core_kernel/Core_kernel/Map/index.html *)
module Dijk = struct
    module T = struct
        type t = int64 * int * int
        let compare = Tuple3.compare ~cmp1:Int64.compare ~cmp2:compare ~cmp3:compare
        let sexp_of_t = Tuple3.sexp_of_t Int64.sexp_of_t Int.sexp_of_t Int.sexp_of_t
    end
    include T
    include Comparator.Make(T)
end

module H = struct
    type t = (Dijk.t, Dijk.comparator_witness) Set.t
    let min_elt h = Option.map (Set.min_elt h) ~f:(fun (dist,v,money) -> (dist, (v,money)))
    let remove_min h = match Set.min_elt h with
        | None -> h
        | Some x -> Set.remove h x
    let add h dist (v,money) = Set.add h (dist, v, money)
    let singleton dist (v,money) = Set.singleton (module Dijk) (dist, v, money)
end

let dijk () = let rec loop mins =
    match H.min_elt mins with
    | None -> ()
    | Some (dist, (v, money)) ->
        let mins = H.remove_min mins in
        if Int64.(dist >= res.{v, money}) then loop mins else begin
        res.{v, money} <- Int64.min res.{v, money} dist;
        (* 銀貨に交換 *)
        let mins =
            let dist = Int64.(dist + snd maisu_jikan_s.(v)) in
            let money = money + fst maisu_jikan_s.(v) in
            if money <= money_inf && Int64.(dist < res.{v, money})
            then ((* res.{v, money} <- dist; *) H.add mins dist (v, money))
            else mins
        in
        (* 別の都市に移動 *)
        let mins = List.fold edges.(v) ~init:mins ~f:begin fun mins e ->
            let dist = Int64.(dist + e.jikan) in
            let v = e.cod in
            let money = money - e.unchin in
            if money >= 0 && Int64.(dist < res.{v, money})
            then ((* res.{v, money} <- dist; *) H.add mins dist (v, money))
            else mins
        end in
        loop mins end
    in loop (H.singleton 0L (0, s))

let () =
    dijk ();
    for v = 1 to n - 1 do
        let res_v = Array2.slice_left res v in
        let rec calc_min acc i =
            if i < Array1.dim res_v
            then calc_min Int64.(min acc res_v.{i}) (i+1)
            else acc
        in
        printf "%Ld\n" @@ calc_min dist_inf 0
    done


Measured memory_bytes: 46276