open Core
open Stdio

let read_line () = In_channel.(input_line_exn stdin)
let rep i0 n f = for i = i0 to n - 1 do
        f ()
    done
let t2_map f (a, b) = (f a, f b)

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] = read_line () |> String.split ~on:' '
let n = Int.of_string n
let m = Int.of_string m
let s = Int64.of_string s
let s = Int64.(to_int_exn @@ min (of_int money_inf) s)

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

let () =
    for i = 1 to m do
        let [s_u; s_v; s_un; s_ji] = read_line () |> String.split ~on:' ' in
        let u = Int.of_string s_u - 1 in
        let v = Int.of_string s_v - 1 in
        let un = Int.of_string s_un in
        let ji = Int64.of_string s_ji 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:(fun _ ->
    read_line () |> String.lsplit2_exn ~on:' ' |> (fun (x,y) ->
    let x = Int.(min (of_string x) money_inf) in
    let y = Int64.of_string y in
    (x,y)))

let used = Array.make_matrix ~dimx:n ~dimy:(money_inf+1) false
let res = Array.make_matrix ~dimx:n ~dimy:(money_inf+1) dist_inf

let rec dijk 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) then dijk mins else begin
        used.(v).(money) <- true;
        res.(v).(money) <- Int64.min res.(v).(money) dist;
        (* 銀貨に交換 *)
        let mins = let money = money + fst maisu_jikan_s.(v) in
            let dist = Int64.(dist + snd maisu_jikan_s.(v)) in
            if money <= money_inf && not used.(v).(money)
            then Set.add mins (dist, v, money) 
            else mins in
        (* 別の都市に移動 *)
        let mins = List.fold edges.(v) ~init:mins ~f:(fun mins ch ->
            let money = money - ch.unchin in
            let dist = Int64.(dist + ch.jikan) in
            let v = ch.cod in
            if money >= 0 && not used.(v).(money)
            then Set.add mins (dist, v, money)
            else mins) in
        dijk mins
        end

module DijkData : (Comparator.S with type t = (int64 * int * int)) = struct
    type t = (int64 * int * int)
    include Comparator.Make (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)
end

let () = dijk (Set.singleton (module DijkData) (0L, 0, s));
    for v = 1 to n - 1 do
        printf "%Ld\n" @@ Option.value_exn (Array.min_elt res.(v) ~compare:Int64.compare)
    done
