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 used = Array2.create int8_signed c_layout n (money_inf+1)
let () = Array2.fill used 0
 *)
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

let dijk () = let rec loop mins =
    match Set.min_elt mins with
    | None -> ()
    | Some ((dist, v, money) as tup) ->
        let mins = Set.remove mins tup in
        (* if used.{v, money} <> 0 then loop mins else begin *) (* 気持ちは if (...) { continue; } *)
        if Int64.(dist >= res.{v, money}) then loop mins else begin
        (* used.{v, money} <- 1 (* true *); *)
        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 && used.{v, money} = 0 *)
            if money <= money_inf && Int64.(dist < res.{v, money})
            then Set.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 && used.{v, money} = 0 *)
            if money >= 0 && Int64.(dist < res.{v, money})
            then Set.add mins (dist, v, money) 
            else mins
        end in
        loop mins end (* continue; のつもりの行のせいで end が入る *)
    in loop (Set.singleton (module Dijk) (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: 46452