#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <cassert>
#include <random>


int main() {
    long long n, m, s; std::cin >> n >> m >> s;
    std::vector<std::vector<long long>> cost(n, std::vector<long long>(n, -1));
    std::vector<std::vector<long long>> minutes(n, std::vector<long long>(n, -1));
    long long sum = 0;
    for (int i = 0; i < m; i++) {
        long long a, b, c, d; std::cin >> a >> b >> c >> d;
        a--; b--;
        cost[a][b] = cost[b][a] = c;
        minutes[a][b] = minutes[b][a] = d;
        sum += c;
    }
    constexpr long long INIT = 1e18;
    if (sum <= s) {
        std::priority_queue<
            std::pair<long long, long long>,
            std::vector<std::pair<long long, long long>>,
            std::greater<std::pair<long long , long long>>> que;
        std::vector<long long> ans(n, INIT);
        que.push({ 0, 0 });
        while (!que.empty()) {
            auto p = que.top();
            que.pop();
            long long dist = p.first;
            long long pos = p.second;
            if (ans[pos] != INIT) continue;
            ans[pos] = dist;
            for (int i = 0; i < n; i++) {
                if (cost[pos][i] == -1) continue;
                if (ans[i] != INIT) continue;
                que.push({ dist + minutes[pos][i], i });
            }
        }
        for (int i = 1; i < n; i++) {
            std::cout << ans[i] << std::endl;
        }
        return 0;
    }

    std::vector<long long> exchange(n), minutes_exchange(n);
    for (int i = 0; i < n; i++) {
        std::cin >> exchange[i] >> minutes_exchange[i];
    }
    using Node = std::pair<long long, std::pair<long long, long long>>;
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> que;
    std::vector<std::vector<long long>>
        ans(n, std::vector<long long>(sum + 2, INIT));
    que.push({ 0, { 0, s } });
    ans[0][s] = 0;
    while (!que.empty()) {
        long long dist = que.top().first;
        long long pos = que.top().second.first;
        long long coin = que.top().second.second;
        que.pop();

        for (int i = 0; i < n; i++) {
            if (cost[pos][i] == -1) continue;
            long long nxtcoin = coin - cost[pos][i];
            long long nxtdist = dist + minutes[pos][i];
            if (nxtcoin < 0) continue;
            if (ans[i][nxtcoin] <= nxtdist) continue;
            ans[i][nxtcoin] = nxtdist;
            que.push({ nxtdist, { i, nxtcoin } });
        }

        long long org_coin = coin;
        while (coin < sum) {
            coin += exchange[pos];
            dist += minutes_exchange[pos];
            if (coin >= sum) break;
            if (ans[pos][coin] <= dist) continue;
            ans[pos][coin] = dist;
            que.push({ dist, {pos, coin} });
        }
        if (org_coin < sum && ans[pos][sum] > dist) {
            ans[pos][sum] = dist;
            que.push({ dist,{ pos, sum } });
        }
    }
    for (int i = 1; i < n; i++) {
        std::cout << *std::min_element(ans[i].begin(), ans[i].end()) << std::endl;
    }
    return 0;
}

Measured memory_bytes: 53512