#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<lint, lint>;
#define print(...) {for(auto x: __VA_ARGS__) cout<<x<<" ";}
#define debug(...) {cout<<#__VA_ARGS__": ";print(__VA_ARGS__);cout<<endl;}

struct Graph {
    struct Edge { int from; int to; lint cost; };
    struct Node {
        Node() : par(-1), done(false), dist(INF) {}
        int index;
        int par;
        bool done;
        lint dist;
        vector<Edge> edge;
    };

    int n;
    vector<Node> nodes;
    vector<Edge> edges;
    const static lint INF = 1e18;

    Graph(int n) : n(n) {
        nodes.resize(n);
        for(int i=0; i<n; i++)  nodes[i].index = i;
    }

    void add_edge(int from, int to, lint cost) {
        nodes[from].edge.push_back(Edge{from, to, cost});
        edges.push_back(Edge{from, to, cost});
    }

    void dijkstra(int s) {
        using Cand = tuple<lint, int, int>; // (dist, index, from)
        priority_queue<Cand, vector<Cand>, greater<Cand>> que;
        que.emplace(0, s, -1);

        while(!que.empty()) {
            lint dist; int index, from;
            tie(dist, index, from) = que.top(); que.pop();
            if(dist >= nodes[index].dist)  continue;
            
            nodes[index].dist = dist;
            nodes[index].par = from;
            for(auto& e : nodes[index].edge) {
                que.emplace(dist + e.cost, e.to, e.from);
            }
        }
    }

    lint shortest_dist(int to) { return nodes[to].dist; }

    vector<int> shortest_path(int to) {
        vector<int> path;
        int index = to;
        while(index != -1) {
            path.push_back(index);
            index = nodes[index].par;
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

int main() {
    lint n, m, s;
    cin >> n >> m >> s;

    map<P, P> ab;
    for(lint i=0; i<m; i++) {
        lint u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        ab[{u,v}] = {a,b};
        ab[{v,u}] = {a,b};
    }

    vector<P> cd(n);
    for(lint i=0; i<n; i++) {
        lint c, d;
        cin >> c >> d;
        cd[i] = {c, d};
    }

    Graph g(n*2501);
    auto id = [&](lint idx, lint money){
        return money*n + idx;
    };

    // 金貨の交換
    for(lint i=0; i<n; i++)
    for(lint money=0; money<=2500; money++) {
        lint c = cd[i].first;
        lint d = cd[i].second;

        lint from = id(i, money);
        lint to = id(i, money+c);
        if(money+c > 2500) continue;

        g.add_edge(from, to, d);
    }

    // 鉄道
    for(lint i=0; i<n; i++)
    for(lint money=0; money<=2500; money++)
    for(lint j=0; j<n; j++) {
        if(ab.count({i,j}) == 0) continue;
        lint a = ab[{i,j}].first;
        lint b = ab[{i,j}].second;

        lint from = id(i, money);
        lint to = id(j, money-a);
        if(money-a<0) continue;

        g.add_edge(from, to, b);
    }

    lint start = id(0, min(s,2500LL));
    g.dijkstra(start);

    for(lint i=1; i<n; i++) {
        lint ans = 1e18;
        for(lint money=0; money<=2500; money++) {
            ans = min(ans, g.shortest_dist(id(i, money)));
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 40872