#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

#ifdef LOCAL
#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define dbg(...) 17;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) { bool f = true; os << "{"; for (const auto &x : c) { if (!f) os << ", "; f = false; os << x; } return os << "}"; }
template<typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template<typename T, typename... Args> void debug(string s, T x, Args... args) { cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...); }

template<class C, bool directed> struct dijkstra {
    int SZ; vector<C> dist;
    vector<vector<pair<int, C>>> adj;
    void init(int _SZ) {
        SZ = _SZ;
        adj.clear();
        adj.resize(SZ);
    }
    void ae(int u, int v, C cost) {
        adj[u].emplace_back(v, cost);
        if (!directed) adj[v].emplace_back(u, cost);
    }
    void gen(int st) {
        dist = vector<C>(SZ, numeric_limits<C>::max());
        typedef pair<C, int> T;
        priority_queue<T, vector<T>, greater<T>> pq;
        auto ad = [&](int a, C b) {
            if (dist[a] <= b) return ;
            pq.push({dist[a] = b, a});
        };
        ad(st, 0);
        while (!pq.empty()) {
            auto x = pq.top();
            pq.pop();
            if (dist[x.second] < x.first) continue;
            for (auto& y: adj[x.second]) {
                ad(y.first, x.first + y.second);
            }
        }
    }
};
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    int cap = 0;
    vector<array<int, 4>> edges;
    vector<int> c(n), d(n);
    for (int i = 0; i < m; i++) {
        int u, v, a, b; cin >> u >> v >> a >> b;
        u--; v--;
        edges.push_back({u, v, a, b});
        cap += a;
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i] >> d[i];
    }
    int verts = (n + 5) * (cap + 5);
    auto label = [&](int vert, int sum) -> int {
        return vert * (cap + 1) + sum;
    };
    dijkstra<ll, true> D;
    D.init(verts);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= cap; j++) {
            int nxt = j + c[i];
            if (nxt >= cap) nxt = cap;
            int v1 = label(i, j);
            int v2 = label(i, nxt);
            D.ae(v1, v2, d[i]);
        }
    }
    for (auto e: edges) {
        int u = e[0];
        int v = e[1];
        int a = e[2];
        int b = e[3];
        for (int j = 0; j <= cap; j++) {
            if (j < a) continue;
            int nxt = j - a;
            int v1 = label(u, j);
            int v2 = label(v, nxt);
            D.ae(v1, v2, b);
        }
        for (int j = 0; j <= cap; j++) {
            if (j < a) continue;
            int nxt = j - a;
            int v1 = label(v, j);
            int v2 = label(u, nxt);
            D.ae(v1, v2, b);
        }
    }
    int start = label(0, min(s, cap));
    D.gen(start);
    for (int t = 1; t < n; t++) {
        ll ans = 1e18;
        for (int j = 0; j <= cap; j++) {
            ans = min(ans, D.dist[label(t, j)]);
        }
        cout << ans << '\n';
    }
    return 0;
}


Measured memory_bytes: 25336