#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate, gcd など
#include <cassert>    // assert
#include <stdexcept>
#include <bitset>
using namespace std;

#define rep(i, a, n) for (int i = a; i < (int)(n); i++)
typedef long long ll;

// GCC, 配列のアクセスなど
#define _GLIBCXX_DEBUG
// Clang, 配列のアクセスなど
#define _LIBCPP_DEBUG 0

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

constexpr int ginka_inf = 50 * 50;
constexpr ll dist_inf = 100000'00000'00000LL;
constexpr int n_inf = 50;
struct edge {
    int cod;
    int unchin;
    ll jikan;
};
int n, m;
int s;
vector<vector<edge>> edges(n_inf);
vector<int> koukan_ginka_s(n_inf);
vector<ll> koukan_jikan_s(n_inf);

vector<vector<bool>> used_dijk(n_inf, vector<bool>(ginka_inf + 1, false));
vector<vector<ll>> res(n_inf, vector<ll>(ginka_inf + 1, dist_inf));

typedef tuple<ll, int, int> dijk_type;
void dijk(const dijk_type &tup) {
    // priority_queue<dijk_type, vector<dijk_type>, greater<dijk_type>> mins;
    set<dijk_type> mins;
    // mins.push(tup);
    mins.insert(tup);
    while (!mins.empty()) {
        ll dist; int v, ginka;
        // tie(dist, v, ginka) = mins.top(); mins.pop();
        tie(dist, v, ginka) = *mins.begin(); mins.erase(mins.begin());
        if (used_dijk[v][ginka]) {
            continue;
        }
        used_dijk[v][ginka] = true;
        res[v][ginka] = min(res[v][ginka], dist);
        {
            auto ginka_ = ginka + koukan_ginka_s[v];
            auto dist_ = dist + koukan_jikan_s[v];
            if (ginka_ <= ginka_inf && !used_dijk[v][ginka_]) {
                // mins.push({dist_, v, ginka_});
                mins.insert({dist_, v, ginka_});
            }
        }
        for (auto e : edges[v]) {
            auto ginka_ = ginka - e.unchin;
            auto dist_ = dist + e.jikan;
            auto v_ = e.cod;
            if (ginka_ >= 0 && !used_dijk[v_][ginka_]) {
                // mins.push({dist_, v_, ginka_});
                mins.insert({dist_, v_, ginka_});
            }
        }
    }
}

int main()
{
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(15); // 浮動小数の表示の精度

    cin >> n >> m >> s;
    s = min(s, ginka_inf);

    edges.resize(n);
    koukan_ginka_s.resize(n);
    koukan_jikan_s.resize(n);
    used_dijk.resize(n);
    res.resize(n);

    rep(i, 0, m) {
        int u, v, un; ll ji;
        cin >> u >> v >> un >> ji;
        u--; v--;
        edges[u].push_back({v, un, ji});
        edges[v].push_back({u, un, ji});
    }

    rep(i, 0, n) {
        int gi, ji;
        cin >> gi >> ji;
        koukan_ginka_s[i] = min(gi, ginka_inf);
        koukan_jikan_s[i] = ji;
    }

    dijk({0LL, 0, s});
    rep(v, 1, n) {
        ll r = dist_inf;
        rep(j, 0, ginka_inf + 1) {
            r = min(r, res[v][j]);
        }
        cout << r << '\n';
    }

    return 0;
}


Measured memory_bytes: 13812