macro_rules !read_value {($iter :expr ,($($t :tt ) ,*) ) =>{($(read_value !($iter ,$t ) ) ,*) } ;($iter :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |read_value !($iter ,$t ) ) .collect ::<Vec <_ >>() } ;($iter :expr ,{chars :$base :expr } ) =>{read_value !($iter ,String ) .chars () .map (|c |(c as u8 -$base as u8 ) as usize ) .collect ::<Vec <usize >>() } ;($iter :expr ,{char :$base :expr } ) =>{read_value !($iter ,{chars :$base } ) [0 ] } ;($iter :expr ,chars ) =>{read_value !($iter ,String ) .chars () .collect ::<Vec <char >>() } ;($iter :expr ,char ) =>{read_value !($iter ,chars ) [0 ] } ;($iter :expr ,usize1 ) =>{read_value !($iter ,usize ) -1 } ;($iter :expr ,$t :ty ) =>{$iter .next () .unwrap () .parse ::<$t >() .unwrap () } ;}
macro_rules !input_inner {($iter :expr ) =>{} ;($iter :expr ,) =>{} ;($iter :expr ,mut $var :ident :$t :tt $($r :tt ) *) =>{let mut $var =read_value !($iter ,$t ) ;input_inner !{$iter $($r ) *} } ;($iter :expr ,mut $var :ident $($r :tt ) *) =>{input_inner !{$iter ,mut $var :usize $($r ) *} } ;($iter :expr ,$var :ident :$t :tt $($r :tt ) *) =>{let $var =read_value !($iter ,$t ) ;input_inner !{$iter $($r ) *} } ;($iter :expr ,$var :ident $($r :tt ) *) =>{input_inner !{$iter ,$var :usize $($r ) *} } ;}
macro_rules !input {(source =$s :expr ,$($r :tt ) *) =>{let mut iter =$s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;(iter =$iter :ident ,$($r :tt ) *) =>{let s ={use std ::io ::Read ;let mut s =String ::new () ;std ::io ::stdin () .read_to_string (&mut s ) .unwrap () ;s } ;let mut $iter =s .split_whitespace () ;input_inner !{$iter ,$($r ) *} } ;($($r :tt ) *) =>{let s ={use std ::io ::Read ;let mut s =String ::new () ;std ::io ::stdin () .read_to_string (&mut s ) .unwrap () ;s } ;let mut iter =s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;}
use std::cmp::Reverse;
use std::collections::BinaryHeap;
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Adjacent {
    pub to: usize,
    pub id: usize,
}
impl Adjacent {
    pub fn new(to: usize, id: usize) -> Adjacent {
        Adjacent { to: to, id: id }
    }
}
#[derive(Clone, Debug, Default)]
pub struct Graph {
    pub vsize: usize,
    pub esize: usize,
    pub graph: Vec<Vec<Adjacent>>,
}
impl Graph {
    pub fn new(vsize: usize) -> Graph {
        Graph {
            vsize: vsize,
            esize: 0,
            graph: vec![vec![]; vsize],
        }
    }
    pub fn add_edge(&mut self, from: usize, to: usize) {
        self.graph[from].push(Adjacent::new(to, self.esize));
        self.esize += 1;
    }
    pub fn add_undirected_edge(&mut self, u: usize, v: usize) {
        self.graph[u].push(Adjacent::new(v, self.esize));
        self.graph[v].push(Adjacent::new(u, self.esize));
        self.esize += 1;
    }
    pub fn vertices(&self) -> std::ops::Range<usize> {
        0..self.vsize
    }
    pub fn adjacency(&self, from: usize) -> &Vec<Adjacent> {
        &self.graph[from]
    }
}
fn main() {
    input! { n, m, s, uvab: [(usize1, usize1, usize, usize); m], cd: [(usize, usize); n] };
    let suma = (uvab.iter().map(|t| t.2).sum::<usize>() + 1) * 2;
    let mut cost = vec![vec![std::usize::MAX; suma + 1]; n];
    let mut g = Graph::new(n);
    for i in 0..m {
        let (u, v, _a, _b) = uvab[i];
        g.add_undirected_edge(u, v);
    }
    cost[0][0] = 0;
    let s = std::cmp::min(s, suma);
    for i in 0..s + 1 {
        cost[0][i] = 0;
    }
    let mut heap = BinaryHeap::new();
    heap.push((Reverse(0), s, 0));
    while let Some((t, k, u)) = heap.pop() {
        let t = t.0;
        let nk = std::cmp::min(suma, k + cd[u].0);
        let nt = t + cd[u].1;
        for i in k + 1..nk + 1 {
            if nt < cost[u][nk] {
                cost[u][i] = nt;
                heap.push((Reverse(nt), i, u));
            }
        }

        for a in g.adjacency(u) {
            if k < uvab[a.id].2 {
                continue;
            }
            let nk = k - uvab[a.id].2;
            if t + uvab[a.id].3 < cost[a.to][nk] {
                let nt = t + uvab[a.id].3;
                cost[a.to][nk] = nt;
                heap.push((Reverse(nt), nk, a.to));
            }
        }
    }
    for i in 1..n {
        let mut ans = std::usize::MAX;
        for j in 0..suma + 1 {
            ans = std::cmp::min(ans, cost[i][j]);
        }
        println!("{}", ans);
    }
}


Measured memory_bytes: 7052