#include <iostream>
#include <vector>
#include <queue>

const long long INF = 1LL << 60;

int main() {
    int N, M, S;
    std::cin >> N >> M >> S;

    std::vector<std::vector<std::pair<int, int>>> g(N);
    std::vector<int> A(M);
    std::vector<long long> B(M);
    int A_max = 0;
    for (int i = 0; i < M; i++) {
        int U, V;
        std::cin >> U >> V >> A[i] >> B[i];
        U--;
        V--;
        g[U].push_back(std::make_pair(V, i));
        g[V].push_back(std::make_pair(U, i));
        A_max = std::max(A_max, A[i]);
    }

    std::vector<int> C(N);
    std::vector<long long> D(N);
    for (int i = 0; i < N; i++)
        std::cin >> C[i] >> D[i];

    int s_max = A_max * (N - 1);

    std::vector<
        std::vector<long long>
    > dist(N, std::vector<long long>(s_max + 1, INF));

    std::priority_queue<
        std::pair<long long, std::pair<int, int>>,
        std::vector<std::pair<long long, std::pair<int, int>>>,
        std::greater<std::pair<long long, std::pair<int, int>>>
    > que;

    {
        int r = std::min(s_max, S);

        dist[0][r] = 0;

        que.push(
            std::make_pair(
                0,
                std::make_pair(0, r)
            )
        );
    }

    while (!que.empty()) {
        auto p = que.top();
        que.pop();

        int t = p.first;
        int u = p.second.first;
        int s = p.second.second;

        for (auto q : g[u]) {
            int v = q.first;
            int i = q.second;

            if (s < A[i]) continue;

            int r = s - A[i];

            if (dist[u][s] + B[i] < dist[v][r]) {
                dist[v][r] = dist[u][s] + B[i];

                que.push(
                    std::make_pair(
                        dist[v][r],
                        std::make_pair(v, r)
                    )
                );
            }
        }

        {
            int r = std::min(s_max, s + C[u]);

            if (dist[u][s] + D[u] < dist[u][r]) {
                dist[u][r] = dist[u][s] + D[u];

                que.push(
                    std::make_pair(
                        dist[u][r],
                        std::make_pair(u, r)
                    )
                );
            }
        }
    }

    for (int i = 1; i < N; i++) {
        long long ans = INF;

        for (int j = 0; j <= s_max; j++)
            ans = std::min(ans, dist[i][j]);

        std::cout << ans << "\n";
    }
}