#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> P1;
typedef pair<P, P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7

#define fi first
#define sc second
#define rep(i, x) for (long long i = 0; i < x; i++)
#define repn(i, x) for (long long i = 1; i <= x; i++)
#define SORT(x) sort(x.begin(), x.end())
#define ERASE(x) x.erase(unique(x.begin(), x.end()), x.end())
#define POSL(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin())
#define POSU(x, v) (upper_bound(x.begin(), x.end(), v) - x.begin())
vector<pair<string, P> > vec;
// vector<vector<int>> data(3, vector<int>(4));

using Weight = ll;
using Flow = ll;
struct Edge {
    ll src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) {}
    Edge(ll s, ll d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, ll a, ll b, Weight w = 1) {
    g[a].emplace_back(a, b, w);
    g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, ll a, ll b, Weight w = 1) { g[a].emplace_back(a, b, w); }

std::vector<Weight> dijkstra(const Graph &g, ll s) {
    const Weight INF = std::numeric_limits<Weight>::max() / 8;
    using state = std::tuple<Weight, ll>;
    std::priority_queue<state> q;
    std::vector<Weight> dist(g.size(), INF);
    dist[s] = 0;
    q.emplace(0, s);
    while (q.size()) {
        Weight d;
        ll v;
        std::tie(d, v) = q.top();
        q.pop();
        d *= -1;
        /* if(v == t) return d; */
        if (dist[v] < d) continue;
        for (auto &e : g[v]) {
            if (dist[e.dst] > dist[v] + e.weight) {
                dist[e.dst] = dist[v] + e.weight;
                q.emplace(-dist[e.dst], e.dst);
            }
        }
    }
    return dist;
}

void solve(long long N, long long M, long long S, std::vector<long long> U, std::vector<long long> V,
           std::vector<long long> A, std::vector<long long> B, std::vector<long long> C, std::vector<long long> D) {
    Graph g(250055);
    rep(i, M) {
        rep(j, 2501) {
            if (j - A[i] >= 0) {
                add_arc(g, U[i] + j * 100, V[i] + (j - A[i]) * 100, B[i]);
                add_arc(g, V[i] + j * 100, U[i] + (j - A[i]) * 100, B[i]);
            }
        }
    }
    rep(i, N) {
        rep(j, 2501) {
            if (i + (j + C[i]) * 100 < 250055) {
                add_arc(g, i + j * 100, i + (j + C[i]) * 100, D[i]);
            }
        }
    }

    vector<Weight> w = dijkstra(g, min(S * 100, 250000LL));

    repn(i, N - 1) {
        ll res = 10000000000000000;
        rep(j, 2501) { res = min(res, w[i + j * 100]); }
        cout << res << endl;
    }
}

int main() {
    long long N;
    scanf("%lld", &N);
    long long M;
    scanf("%lld", &M);
    long long S;
    scanf("%lld", &S);
    std::vector<long long> U(M);
    std::vector<long long> V(M);
    std::vector<long long> A(M);
    std::vector<long long> B(M);
    for (int i = 0; i < M; i++) {
        scanf("%lld", &U[i]);
        scanf("%lld", &V[i]);
        U[i]--;
        V[i]--;
        scanf("%lld", &A[i]);
        scanf("%lld", &B[i]);
    }
    std::vector<long long> C(N);
    std::vector<long long> D(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &C[i]);
        scanf("%lld", &D[i]);
    }
    solve(N, M, S, std::move(U), std::move(V), std::move(A), std::move(B), std::move(C), std::move(D));
    return 0;
}


Measured memory_bytes: 40732