#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ull = uint64_t;
const ll INF = 9e18;

ll nodid(ll node, ll money, ll maxmoney) {
    return node * (maxmoney + 1) + money;
}

void print() { cout << endl; }
template <typename Head, typename... Tail>
void print(Head head, Tail... tail) {
    int size = sizeof...(Tail);
    cout << head;
    if (size > 0) {
        cout << " ";
    }
    print(tail...);
}

void print0() {}
template <typename Head, typename... Tail>
void print0(Head head, Tail... tail) {
    cout << head;
    print0(tail...);
}

struct edge {
    ll u;
    ll v;
    ll cost;
};
bool operator<=(const edge& lhs, const edge& rhs) {
    return lhs.cost <= rhs.cost;
}
bool operator<(const edge& lhs, const edge& rhs) {
    return lhs.cost < rhs.cost;
}
bool operator>=(const edge& lhs, const edge& rhs) {
    return lhs.cost >= rhs.cost;
}
bool operator>(const edge& lhs, const edge& rhs) {
    return lhs.cost > rhs.cost;
}
bool operator==(const edge& lhs, const edge& rhs) {
    return lhs.cost == rhs.cost;
}
bool operator!=(const edge& lhs, const edge& rhs) {
    return lhs.cost != rhs.cost;
}

void dijkstra(ll start, vector<vector<edge>>& edgemap, vector<ll>& min_cost) {
    vector<bool> done(edgemap.size(), false);
    priority_queue<edge, vector<edge>, greater<edge>> pq;

    pq.push(edge{u : -1, v : start, cost : 0});
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        if (done[e.v]) {
            continue;
        }
        done[e.v] = true;
        min_cost[e.v] = e.cost;
        for (auto next_e : edgemap[e.v]) {
            if (!done[next_e.v]) {
                edge total_next_e = next_e;
                total_next_e.cost = e.cost + next_e.cost;
                pq.push(total_next_e);
            }
        }
    }
}

struct edgtime {
    ll u;
    ll v;
    ll money;
    ll time;
};
int main() {
    ll N, M, S;
    cin >> N >> M >> S;
    ll maxmoney = (N + 1) * 50;

    vector<edgtime> edgtimes(M);
    for (ll i = 0; i < M; i++) {
        edgtime ee;
        cin >> ee.u >> ee.v >> ee.money >> ee.time;
        edgtimes[i] = ee;
    }

    vector<ll> C(N + 1);
    vector<ll> D(N + 1);
    for (ll i = 1; i <= N; i++) {
        cin >> C[i] >> D[i];
    }
    vector<vector<edge>> edgemap((maxmoney + 1) * (N + 1) + 1);

    for (ll i = 1; i <= N; i++) {
        for (ll money = 0; money <= maxmoney; money++) {
            ll nextmoney = min(money + C[i], maxmoney);
            auto src = nodid(i, money, maxmoney);
            auto dest = nodid(i, nextmoney, maxmoney);
            edgemap[src].push_back({src, dest, D[i]});
        }
    }
    for (auto et : edgtimes) {
        for (ll money = 0; money <= maxmoney; money++) {
            ll nextmoney = money - et.money;
            if (nextmoney >= 0) {
                ll src_uv = nodid(et.u, money, maxmoney);
                ll dest_uv = nodid(et.v, nextmoney, maxmoney);

                ll src_vu = nodid(et.v, money, maxmoney);
                ll dest_vu = nodid(et.u, nextmoney, maxmoney);

                edgemap[src_uv].push_back({src_uv, dest_uv, et.time});
                edgemap[src_vu].push_back({src_vu, dest_vu, et.time});
            }
        }
    }

    ll s = min(S, maxmoney);
    vector<ll> min_cost((maxmoney + 1) * (N + 1) + 1, INF);
    dijkstra(nodid(1, s, maxmoney), edgemap, min_cost);

    for (ll t = 2; t <= N; t++) {
        ll mc = INF;
        for (ll money = 0; money <= maxmoney; money++) {
            mc = min(min_cost[nodid(t, money, maxmoney)], mc);
        }
        print(mc);
    }
}


Measured memory_bytes: 35560