#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>
#include <cassert>


using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<n;++i)
#define FOR(i, a, b) for(int i=a;i<b;++i)
#define RREP(i, n) for(int i=n-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=b-1;i>=a;--i)

#define all(x) begin(x),end(x)
#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 10;

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> p) {
    os << p.first << ":" << p.second;
    return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

// edit

using Int = ll;

template<typename T = int,
        typename E = int,
        typename F = function<T(T, E)>,
        typename Compare = function<bool(T, T) >>
class Dijkstra {
public:
    Int N;
    T s_value;
    T init_value;
    F f;
    Compare cmp;

    vector<T> dist;
    vector<vector<pair<int, E>>>
            G; // first : index, second : E


    Dijkstra(Int N, T init_value = INF, T s_value = 0,
             F f = [](T l, E r) { return l + r; },
             Compare cmp = [](T l, T r) { return l > r; }
    ) : N(N), s_value(s_value), init_value(init_value), f(f), cmp(cmp) {
        dist.resize(N, init_value);
        G.resize(N);
    }

    void add_edge(int f, int t, E e) {
        G[f].push_back(make_pair(t, e));
    }

    void compute(int s) {
        using P = pair<T, int>;
        auto pq_cmp = [this](P l, P r) -> bool {
            return cmp(l.first, r.first);
        };
        priority_queue<P, vector<P>, decltype(pq_cmp)> que(pq_cmp);
        fill(dist.begin(), dist.end(), init_value);
        dist[s] = s_value;

        que.push(P(dist[s], s));

        while (!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;

//            if (!cmp(dist[v], p.first) && (dist[v] != p.first)) continue;
            if (cmp(p.first, dist[v])) continue;

            for (int i = 0; i < G[v].size(); i++) {
                int to_idx = G[v][i].first;
                E to_e = G[v][i].second;

                if (cmp(dist[to_idx], f(dist[v], to_e)) && !(dist[to_idx] == init_value && dist[v] == init_value)) {
                    dist[to_idx] = f(dist[v], to_e);
                    que.push(P(dist[to_idx], to_idx));
                }
            }
        }
    }

    T get_dist(int v) {
        return dist[v];
    }


};

void solve() {
    int N, M;
    ll S;
    cin >> N >> M;
    cin >> S;
    chmin(S, 2999ll);

    vector<vector<ll>> A(N, vector<ll>(N, LINF));
    vector<vector<ll>> B(N, vector<ll>(N, LINF));
    vector<ll> C(N);
    vector<ll> D(N);


    REP(i, M) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        A[u][v] = A[v][u] = a;
        B[u][v] = B[v][u] = b;
    }

    REP(i, N) {
        int c, d;
        cin >> c >> d;
        C[i] = c;
        D[i] = d;
    }

    // vertex, money
    auto conv = [&](int u, int x) {
        return u * 3000 + x;
    };

    Dijkstra<ll> dij(3000 * N, LINF);

    FOR(i, 0, N) {
        // 両替
        FOR(x, 0, 3000) {
            auto from = conv(i, x);
            auto to = conv(i, min(2999ll, x + C[i]));
            int cost = D[i];

//            cerr << from << " " << to << ' ' << cost << endl;
            dij.add_edge(from, to, cost);
        }

        FOR(j, 0, N) {
            for (int x = 0; x < 3000; ++x) {
                if (x >= A[i][j]) {
                    auto from = conv(i, x);
                    auto to = conv(j, x - A[i][j]);
                    int cost = B[i][j];
                    dij.add_edge(from, to, cost);
//                    cerr << from << " " << to << ' ' << cost << endl;
                }
            }
        }
    }

    dij.compute(conv(0, S));

    for (int i = 1; i < N; ++i) {
        ll ans = LINF;
        for (int x = 0; x <= 2999; ++x) {
            ll tmp = dij.get_dist(conv(i, x));
            chmin(ans, tmp);
        }
        cout << ans << endl;
    }


}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());

    solve();


    return 0;
}


Measured memory_bytes: 19352