#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>

long long cost[50][50];
long long minutes[50][50];
long long ans[50][50 * 50 + 2];
long long exchange[50];
long long minutes_exchange[50];

int main() {
    int n, m; long long s; std::cin >> n >> m >> s;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cost[i][j] = -1;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) minutes[i][j] = -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) s = sum;

    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;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < sum + 2; j++) {
            ans[i][j] = INIT;
        }
    }
    que.push({ 0,{ 0, s } });
    bool vis[50] = {};
    int cnt = 0;
    while (!que.empty()) {
        auto node = move(que.top());
        que.pop();
        long long dist = node.first;
        long long pos = node.second.first;
        long long coin = node.second.second;
        if (ans[pos][coin] != INIT) continue;
        ans[pos][coin] = dist;
        if (!vis[pos]) {
            vis[pos] = true;
            cnt++;
            if (cnt >= n) {
                break;
            }
        }

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

        if (coin < sum) {
            long long nxtcoin = std::min(sum, coin + exchange[pos]);
            long long nxtdist = dist + minutes_exchange[pos];
            if (ans[pos][nxtcoin] != INIT) continue;
            que.push({ nxtdist, {pos, nxtcoin} });
        }
     }
    for (int i = 1; i < n; i++) {
        std::cout << *std::min_element(ans[i], ans[i] + sum + 1) << std::endl;
    }
    return 0;
}
