extern crate proconio;
use proconio::{fastout, input, marker::Usize1};

/*
References
Ahuja, R. K., Mehlhorn, K., Orlin, J., & Tarjan, R. E. (1990).
Faster algorithms for the shortest path problem.
Journal of the ACM (JACM), 37(2), 213-223.
*/

use std::cmp;
use std::mem;

pub struct RadixHeap<V> {
    buckets: Box<[Bucket<V>]>,
}

struct Bucket<V> {
    start: u64,
    data: Vec<(u64, V)>,
}

impl<V> RadixHeap<V> {
    pub fn new(c: u64) -> Self {
        let b = 64 - c.leading_zeros() as usize + 2;
        let buckets = (0..b)
            .map(|i| Bucket {
                start: Self::size_sum(i),
                data: Vec::new(),
            })
            .collect::<Vec<_>>();
        Self {
            buckets: buckets.into_boxed_slice(),
        }
    }

    pub fn push(&mut self, key: u64, value: V) {
        let b = self.buckets
            .iter_mut()
            .rev()
            .find(|b| b.start <= key)
            .expect("monotonicity was violated.");
        b.data.push((key, value));
    }

    pub fn pop(&mut self) -> Option<(u64, V)> {
        let min_pos = self.buckets.iter().position(|b| !b.data.is_empty());
        min_pos.map(|i| {
            if i != 0 {
                let data = mem::replace(&mut self.buckets[i].data, Vec::new());
                let min_key = data.iter().map(|&(key, _)| key).min().unwrap();
                self.buckets[0].start = min_key;
                let end = self.buckets.get(i + 1).map_or(std::u64::MAX, |b| b.start);
                for (i, b) in self.buckets[..=i].iter_mut().enumerate() {
                    b.start = cmp::min(end, min_key + Self::size_sum(i));
                }
                for d in data {
                    let b = self.buckets[..i]
                        .iter_mut()
                        .rev()
                        .find(|b| b.start <= d.0)
                        .unwrap();
                    b.data.push(d);
                }
            }
            self.buckets[0].data.pop().unwrap()
        })
    }

    fn size_sum(i: usize) -> u64 {
        match i {
            0 => 0,
            i => 1 << i - 1,
        }
    }
}

#[fastout]
fn main() {
    input!{
        n: usize,
        m: usize,
        s: u32,
        es: [(Usize1, Usize1, usize, u64); m],
        vs: [(u32, u64); n],
    }
    let lim = es.iter().map(|&(_, _, a, _)| a).max().unwrap() * (n - 1) + 1;
    let s = cmp::min(s, (lim - 1) as u32) as usize;
    let vs = vs.into_iter()
        .map(|(c, d)| (cmp::min(c, (lim - 1) as u32) as usize, d))
        .collect::<Vec<_>>();
    let mut heap = RadixHeap::new(cmp::max(
        es.iter().map(|&(_, _, _, b)| b).max().unwrap(),
        vs.iter().map(|&(_, d)| d).max().unwrap(),
    ));
    let mut g = vec![Vec::new(); n];
    for (u, v, a, b) in es {
        g[u].push((v, a, b));
        g[v].push((u, a, b));
    }

    let mut dist = vec![std::u64::MAX; n * lim];
    dist[0 * lim + s] = 0;
    heap.push(0, (0, s));
    while let Some((t, (v, k))) = heap.pop() {
        let i = v * lim + k;
        if dist[i] < t {
            continue;
        }
        {
            let &(c, d) = &vs[v];
            if k + c < lim {
                let j = v * lim + k + c;
                if t + d < dist[j] {
                    dist[j] = t + d;
                    heap.push(dist[j], (v, k + c));
                }
            }
        }
        for &(u, a, b) in &g[v] {
            if k >= a {
                let j = u * lim + k - a;
                if t + b < dist[j] {
                    dist[j] = t + b;
                    heap.push(dist[j], (u, k - a));
                }
            }
        }
    }
    for t in 1..n {
        println!(
            "{}",
            dist[t * lim..t * lim + lim].iter().copied().min().unwrap()
        );
    }
}


Measured memory_bytes: 7168