#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define INF (long long)(10e17)

struct City {
    vector<int> connections;
    vector<int> fares;
    vector<long long> travel_length;
};

long long spent_times[50][50001];

int main(void)
{
    int cities_count;
    int lines_count;
    long long initial_silvers;
    vector<long long> exchange_lengths;
    vector<long long> exchange_rates;
    vector<City> city_web;

    cin >> cities_count >> lines_count >> initial_silvers;

    for(int i = 0; i < cities_count; i++){
        City city;
        city_web.push_back(city);
    }
    exchange_rates.resize(cities_count);
    exchange_lengths.resize(cities_count);

    for(int i = 0; i < lines_count; i++){
        int c1, c2;
        int f;
        int t_l;
        cin >> c1 >> c2 >> f >> t_l;

        city_web[c1 - 1].connections.push_back(c2 - 1);
        city_web[c1 - 1].fares.push_back(f);
        city_web[c1 - 1].travel_length.push_back(t_l);
        city_web[c2 - 1].connections.push_back(c1 - 1);
        city_web[c2 - 1].fares.push_back(f);
        city_web[c2 - 1].travel_length.push_back(t_l);
    }

    for(int i = 0; i < cities_count; i++){
        int e_r, e_l;
        cin >> e_r >> e_l;
        exchange_rates[i] = e_r;
        exchange_lengths[i] = e_l;
    }

    queue<pair<int, int> > next_search;

    for(int i = 0; i < 50; i++){
        for(int j = 0; j < 50001; j++){
            spent_times[i][j] = INF;
        }
    }

    if(initial_silvers > 2500){
        initial_silvers = 2500;
    }
    next_search.push(make_pair(0, initial_silvers));
    spent_times[0][initial_silvers] = 0;

    while(!next_search.empty()){
        int searching_pos = next_search.front().first;
        int searching_sil = next_search.front().second;
        next_search.pop();

        int exchanged_silver = min((long long)(2500), searching_sil + exchange_rates[searching_pos]);
        long long &memo_time = spent_times[searching_pos][exchanged_silver];
        long long exchanged_time = spent_times[searching_pos][searching_sil] + exchange_lengths[searching_pos];
        if(memo_time > exchanged_time){
            memo_time = (long long)(exchanged_time);
            pair<int, int> exchanged = make_pair(searching_pos, exchanged_silver);
            next_search.push(exchanged);
        }

        const vector<int> &connections = city_web[searching_pos].connections;
        for(int i = 0; i < int(connections.size()); i++){
            int fare = city_web[searching_pos].fares[i];
            if(fare <= searching_sil){
                long long &memo_time = spent_times[connections[i]][searching_sil - fare];
                int travel_len = city_web[searching_pos].travel_length[i];
                long long moved_time = spent_times[searching_pos][searching_sil] + travel_len;
                if(memo_time > moved_time){
                    memo_time = (long long)(moved_time);
                    pair<int, int> moved = make_pair(connections[i], searching_sil - fare);
                    next_search.push(moved);
                }
            }
        }
    }

    for(int i = 1; i < cities_count; i++){
        long long fastest = INF;
        for(int j = 0; j < 50001; j++){
            if(fastest > spent_times[i][j]){
                fastest = spent_times[i][j];
            }
        }
        cout << fastest << endl;
    }

    return 0;
}


Measured memory_bytes: 23500