#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, U, V, W, X, Y, Z, S;
string T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

//0-indexedに注意
class Graph {
    struct edge {
        int from, to, cost;
        edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
    };

public:
    int verN;
    int edgeN = 0;
    vector<edge> edge_set;
    vector<vector<pair<int, pair<int, int>>>> adj_list;
    Graph(int verN) : verN(verN), adj_list(verN) {}

    void add_directed_edge(int from, int to, int cost1, int cost2) {
        adj_list[from].push_back(make_pair(to, make_pair(cost1, cost2)));
        edgeN += 1;
    }

    void add_undirected_edge(int from, int to, int cost1, int cost2) {
        adj_list[from].push_back(make_pair(to, make_pair(cost1, cost2)));
        adj_list[to].push_back(make_pair(from, make_pair(cost1, cost2)));
        edgeN += 2;
    }

    vector<vector<int>> dijkstra(int startNode, int startState, int stateN) {
        vector<vector<int>> d(stateN + 1, vector<int>(verN, LLINF));
        d[startState][startNode] = 0;
        using P = pair<int, int>;
        priority_queue<pair<int, P>, vector<pair<int, P>>, greater<pair<int, P>>> pq;
        vector<vector<int>> used(stateN + 1, vector<int>(verN, 0));
        pq.push(make_pair(0, P(startNode, startState)));
        while (!pq.empty()) {
            auto now = pq.top();
            int nowNode = now.second.first;
            int nowState = now.second.second;
            pq.pop();
            used[nowState][nowNode] = 1;
            for (auto adj_pair : adj_list[nowNode]) {
                int adjNode = adj_pair.first;
                int cost = adj_pair.second.first;
                int adjState = nowState - adj_pair.second.second;
                adjState = min(stateN, adjState);
                if (adjState < 0)
                    continue;
                if (used[adjState][adjNode])
                    continue;
                if (d[adjState][adjNode] > d[nowState][nowNode] + cost) {
                    d[adjState][adjNode] = d[nowState][nowNode] + cost;
                    pq.push(make_pair(d[adjState][adjNode], make_pair(adjNode, adjState)));
                }
            }
        }
        return d;
    }
};

signed main() {
    cin >> N >> M >> S;
    Graph g(N);
    REP(i, M) {
        cin >> U >> V >> A >> B;
        U--, V--;
        g.add_undirected_edge(U, V, B, A);
    }
    REP(i, N) {
        cin >> C >> D;
        g.add_directed_edge(i, i, D, -C);
    }
    int stateN = 5000;
    S = min(S, (ll)stateN);
    auto d = g.dijkstra(0, S, stateN);
    vector<ll> res(N, LLINF);
    REP(st, stateN + 1)
    REP(i, g.verN) {
        res[i] = min(d[st][i], res[i]);
    }
    REP(i, N) {
        if (i == 0)
            continue;
        cout << res[i] << endl;
    }
}

Measured memory_bytes: 13684