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 = int * Dijk.t Array.t
    let zero = (0L, 0, 0)
    let to_tup dist (v,money) = (dist, v, money)
    let of_tup (dist,v,money) = (dist, (v, money))
    let min_elt (last, h) = if last = 0 then None
        else Some (of_tup h.(1))
    let remove_min (last, h) = if last = 0 then (last, h) else begin
        h.(1) <- h.(last);
        let last = last - 1 in
        let rec loop i = if 2 * i > last then () (* 子なし *)
            else if 2 * i = last then (* 子1人 *)
                if Dijk.compare h.(2 * i) h.(i) >= 0 then () else Array.swap h (2 * i) i
            else
                let j = if Dijk.compare h.(2 * i + 1) h.(2 * i) >= 0
                    then 2 * i
                    else 2 * i + 1
                in
                if Dijk.compare h.(j) h.(i) >= 0 then ()
                else (Array.swap h j i; loop j)
        in
        loop 1;
        (last, h)
        end
    let add (last, h) dist x =
        let last = last + 1 in
        let h = if last >= Array.length h
            then begin
                let h2 = Array.create ~len:(2 * Array.length h) zero in
                Array.blit h 0 h2 0 last;
                h2
            end else h
        in
        let rec loop i = if i = 1 then ()
            else if Dijk.compare h.(i) h.(i / 2) >= 0 then ()
            else (Array.swap h i (i / 2); loop (i / 2))
        in
        h.(last) <- to_tup dist x;
        loop last;
        (last, h)
    let singleton dist x = (1, Array.create ~len:100000 (to_tup dist x))
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: 22732