use std::cmp;
use std::collections::*;
use std::cmp::Ordering;

pub struct Scanner {
    line: Vec<String>,
    idx: usize,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        return Scanner {
            line: vec![],
            idx: 0,
        };
    }
    fn next<T: std::str::FromStr>(&mut self) -> T {
        if self.idx == self.line.len() {
            let mut buffer = String::new();
            std::io::stdin().read_line(&mut buffer).ok();
            let a: Vec<&str> = buffer.trim().split(' ').collect();
            self.line = a.iter().map(|&s| String::from(s)).collect();
            self.idx = 0;
        }
        let ret: T = self.line[self.idx].parse::<T>().ok().expect("Parse error.");
        self.idx += 1;
        ret
    }
    fn next_string(&mut self) -> Vec<char> {
        let s: String = self.next();
        return s.chars().collect::<Vec<char>>();
    }
    fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        let mut v: Vec<T> = Vec::with_capacity(n);
        for _i in 0..n {
            v.push(self.next());
        }
        v
    }
}


#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
    city: usize,
    ginka: usize,
    time: i64,
}


impl Ord for State {
    fn cmp(&self, other: &State) -> Ordering {
        self.time.cmp(&other.time).reverse()
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &State) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}



fn main(){
    let mut scan = Scanner::new();
    let n:usize = scan.next();
    let m:usize = scan.next();
    let s:usize = scan.next();
    let mut edge: Vec<Vec<(usize, usize, i64)>> = vec![Vec::new(); n];
    let mut city: Vec<(usize, i64)> = Vec::with_capacity(n);
    for _ in 0..m {
        let u:usize = scan.next();
        let v:usize = scan.next();
        let a:usize = scan.next();
        let b:i64 = scan.next();
        edge[u - 1].push((v - 1, a, b));
        edge[v - 1].push((u - 1, a, b));
    }
    for _ in 0..n {
        let c:usize = scan.next();
        let d:i64 = scan.next();
        city.push((c, d));
    }
    
    let max: usize = 50 * n + 1;
    let mut dp: Vec<Vec<i64>> = vec![vec![i64::max_value(); max + 1]; n];

    let mut pq = BinaryHeap::with_capacity(n* max);
    dp[0][cmp::min(max, s)] = 0;
    pq.push(State{city:0, ginka:cmp::min(max, s), time:0});

    while let Some(st) = pq.pop() {
        if dp[st.city][st.ginka] < st.time {
            continue;
        }
        for i in 0..st.ginka {
            dp[st.city][i] = cmp::min(dp[st.city][i], st.time);
        }

        for i in 1.. {
            let g = cmp::min(max, st.ginka + i * city[st.city].0);
            let t = st.time + i as i64 * city[st.city].1;

            if t < dp[st.city][g] {
                dp[st.city][g] = t;
                pq.push(State{city:st.city, ginka:g, time:t});
            }
            if max <= g {
                break;
            }
        }

        for t in &edge[st.city] {
            let (u, a, b) = *t;
            if st.ginka < a {
                continue;
            }
            if st.time + b < dp[u][st.ginka - a] {
                dp[u][st.ginka - a] = st.time + b;
                pq.push(State{city:u, ginka:st.ginka - a, time: st.time + b});
            }
        }
    }
    //println!("{:?}", dp);

    for i in 1..n {
        let mut ans: i64 = i64::max_value();
        for j in 0..max {
            ans = cmp::min(ans, dp[i][j]);
        }
        println!("{}", ans);
    }
}


Measured memory_bytes: 20436