#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, n) for (int i = 1; i <= (n); ++i)
#define repd(i, n) for (int i = (n - 1); i >= 0; --i)
#define repds(i, n) for (int i = (n); i > 0; --i)
#define loop(i, x, n) for (int i = (x); i < (n); ++i)
#define loops(i, x, n) for (int i = (x); i <= (n); ++i)
#define loopd(i, x, n) for (int i = (x); i > (n); --i)
#define loopds(i, x, n) for (int i = (x); i >= (n); --i)
#define itrep(i, a) for (auto i = begin(a); i != end(a); ++i)
#define itrepd(i, a) for (auto i = rbegin(a); i != rend(a); ++i)
#define each(i, x) for (auto &i : x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using ld = long double;
template <class T>
using priority_queuel = priority_queue<T, vector<T>, greater<T>>;
constexpr ll inf = static_cast<ll>(1e18);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e18;
constexpr double eps = 1e-9;
ll mod = static_cast<ll>(1e9 + 7);
template <class T>
constexpr int sz(const T &a) { return (int)a.size(); }
template <class T>
constexpr T pow2(const T a) { return a * a; }
template <class T, class... Args>
constexpr void mins(T &a, Args... args) { a = min<T>({a, args...}); }
template <class T, class... Args>
constexpr void maxs(T &a, Args... args) { a = max<T>({a, args...}); }
template <class A, int N, class T>
void fillArray(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

template <class T, class U>
struct FirstPair {
    T first;
    U second;
    FirstPair(T fi, U se) : first(fi), second(se) {}
    bool operator<(const FirstPair &x) const {
        return first < x.first;
    }
    bool operator>(const FirstPair &x) const {
        return first > x.first;
    }
};

int n, m;
ll s;
vector<tuple<int, int, ll>> g[55];
ll c[55], d[55];
ll dist[55][55 * 55];
void solve() {
    cin >> n >> m >> s;
    int ma = 0;
    rep(i, m) {
        int u, v, a;
        ll b;
        cin >> u >> v >> a >> b;
        --u, --v;
        maxs(ma, a);
        g[u].emplace_back(v, a, b);
        g[v].emplace_back(u, a, b);
    }
    rep(i, n) cin >> c[i] >> d[i];

    auto sc = (int)min<ll>(ma * (n - 1), s);
    fillArray(dist, inf);
    priority_queuel<FirstPair<ll, pair<int, int>>> que;
    que.emplace(0, make_pair(0, sc));
    dist[0][sc] = 0;
    while (!que.empty()) {
        auto p = que.top();
        que.pop();
        auto v = p.second.first;
        auto co = p.second.second;
        auto t = dist[v][co];
        if (p.first != t) continue;
        for (ll i = 1; co + c[v] * (i - 1) < ma * (n - 1); ++i) {
            auto nc = (int)min<ll>(ma * (n - 1), co + c[v] * i);
            auto nt = t + d[v] * i;
            if (dist[v][nc] > nt) {
                dist[v][nc] = nt;
                que.emplace(nt, make_pair(v, nc));
            }
        }

        rep(i, sz(g[v])) {
            auto &[nv, a, b] = g[v][i];
            auto nc = co - a;
            auto nt = t + b;
            if (nc < 0) continue;
            if (dist[nv][nc] > nt) {
                dist[nv][nc] = nt;
                que.emplace(nt, make_pair(nv, nc));
            }
        }
    }

    reps(i, n - 1) {
        ll ans = inf;
        rep(j, ma * (n - 1) + 1) mins(ans, dist[i][j]);
        cout << ans << endl;
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout.flush();
    return 0;
}


Measured memory_bytes: 37448