macro_rules! input {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::cmp::{Reverse, min};
use std::collections::BinaryHeap;

#[derive(Debug,PartialEq,Eq,Clone,Copy,PartialOrd,Ord)]
struct State {
    time: Reverse<usize>,
    coins_held: usize,
    position: usize,
}

#[derive(Debug,PartialEq,Eq,Clone,Copy)]
struct Edge {
    to: usize,
    cost: usize,
    time: usize,
}

const COIN_LIMIT: usize = 2500;

fn main() {
    let stdin = std::io::stdin();
    let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
    let mut next = move || -> String{
        bytes
            .by_ref()
            .map(|r|r.unwrap() as char)
            .skip_while(|c|c.is_whitespace())
            .take_while(|c|!c.is_whitespace())
            .collect()
    };
    input! {next,
        num_vertices: usize, // <= 50
        num_edges: usize, // <= 100
        starting_coins: usize,
        edge_read: [(usize1, usize1, usize, usize); num_edges],
        exchange_counters: [(usize, usize); num_vertices], // coin_gain, time_taken
    }

    let mut edges = vec![Vec::new(); num_vertices];
    for (v1, v2, cost, time) in edge_read {
        edges[v1].push(Edge {
            to: v2,
            cost: cost,
            time: time,
        });
        edges[v2].push(Edge {
            to: v1,
            cost: cost,
            time: time,
        });
    }
    // dbg!(&edges);

    // best time for [position] and [coins_held]
    let mut best_times = vec![vec![std::usize::MAX; COIN_LIMIT+1]; num_vertices];
    let mut pq = BinaryHeap::new();
    pq.push(State {
        time: Reverse(0),
        coins_held: min(starting_coins, COIN_LIMIT),
        position: 0,
    });
    while let Some(state) = pq.pop() {
        let Reverse(state_time) = state.time;
        for &edge in &edges[state.position] {
            if state.coins_held >= edge.cost {
                let new_time = state_time + edge.time;
                let coins_remaining = state.coins_held - edge.cost;
                if new_time < best_times[edge.to][coins_remaining] {
                    best_times[edge.to][coins_remaining] = new_time;
                    pq.push(State {
                        time: Reverse(new_time),
                        coins_held: coins_remaining,
                        position: edge.to,
                    });
                }
            }
        }

        let new_time = state_time + exchange_counters[state.position].1;
        let new_coins = min(state.coins_held + exchange_counters[state.position].0, COIN_LIMIT);
        if new_time < best_times[state.position][new_coins] {
            best_times[state.position][new_coins] = new_time;
            pq.push(State {
                time: Reverse(new_time),
                coins_held: new_coins,
                position: state.position,
            });
        }
    }
    for v in best_times.into_iter().skip(1) {
        println!("{}", v.into_iter().min().unwrap());
    }
}


Measured memory_bytes: 4640