//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <complex>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;
constexpr ll LL_MAX = numeric_limits<ll>::max();
constexpr ull ULL_MAX = numeric_limits<ull>::max();

template<typename T>
vector<T> make_vec_nd(T init, ll size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, ll size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a)-1; i >= (b); i--)

struct ListCostGraph {
    struct Edge {
        ll from;
        ll to;
        ll cost;
    };
    vector<vector<Edge>> edges;
    
    ListCostGraph(ll size) { edges.resize(size); }
    
    void add_edge(ll from, ll to, ll cost) {
        edges[from].push_back(Edge{from, to, cost});
    }
    
    void add_edge_bidir(size_t a, size_t b, ll cost) {
        add_edge(a, b, cost);
        add_edge(b, a, cost);
    }
    
    vector<ll> dijkstra(ll s) {
        // O(E logV)
        vector<ll> dist(edges.size(), numeric_limits<ll>::max());
        struct P {
            size_t vertex;
            ll distance;
            P(size_t vertex, ll distance)
            : vertex(vertex)
            , distance(distance) {}
        };
        auto compare = [](const P& lhs, const P& rhs) {
            return lhs.distance > rhs.distance;
        };
        priority_queue<P, vector<P>, decltype(compare)> que(compare);
        dist[s] = 0;
        que.push(P(s, 0));
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            size_t v = p.vertex;
            ll d = p.distance;
            if (dist[v] < d) {
                continue;
            }
            for (int i = 0; i < edges[v].size(); i++) {
                const Edge& e = edges[v][i];
                ll new_dist = dist[v] + e.cost;
                if (dist[e.to] <= new_dist) {     // eを使っても最短経路が改善しないとき
                    continue;
                }
                dist[e.to] = new_dist;
                que.push(P(e.to, new_dist));
            }
        }
        return dist;
    }
};

int main() {
    ll N, M, S;
    cin >> N >> M >> S;
    ll MAX_COIN = 50 * 100;
    ListCostGraph graph((MAX_COIN + 1) * N);
    if (S > MAX_COIN) {
        S = MAX_COIN;
    }
    rep(i,0,M) {
        ll U, V, cost, time;
        cin >> U >> V >> cost >> time;
        U--;
        V--;
        rep(coin,0,MAX_COIN+1) {
            if (cost > coin) {
                continue;
            }
            {
                ll u = U * (MAX_COIN+1) + coin;
                ll v = V * (MAX_COIN+1) + (coin - cost);
                graph.add_edge(u, v, time);
            }
            {
                ll u = U * (MAX_COIN+1) + (coin - cost);
                ll v = V * (MAX_COIN+1) + coin;
                graph.add_edge(v, u, time);
            }
        }
    }
    rep(i,0,N) {
        ll rate, time;
        cin >> rate >> time;
        rep(coin,0,MAX_COIN+1) {
            ll next_coin = coin + rate;
            if (next_coin > MAX_COIN) {
                next_coin = MAX_COIN;
            }
            ll u = i * (MAX_COIN+1) + coin;
            ll v = i * (MAX_COIN+1) + next_coin;
            graph.add_edge(u, v, time);
        }
    }
    vector<ll> dist = graph.dijkstra(S);
    rep(i,1,N) {
        ll ans = numeric_limits<ll>::max();
        rep(coin,0,MAX_COIN+1) {
            ll u = i * (MAX_COIN+1) + coin;
            ans = min(ans, dist[u]);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 56680