#include <bits/stdc++.h>

using namespace std;
using ll = long long int;
constexpr ll M = 1e9 + 7;
constexpr ll INF = LLONG_MAX>>4;
inline ll sum_1(const ll n) { return ((n * (n + 1)) / 2) % M; }
inline ll sum_2(const ll n) { return ((n * (n + 1) * (2 * n + 1)) / 6) % M; }
inline ll sum_3(const ll n) { return (((n * (n + 1)) / 2) % M * ((n * (n + 1)) / 2) % M) % M; }
inline ll sum_1(const ll i, const ll j) { return (sum_1(j) - sum_1(i - 1) + M) % M; }
inline ll sum_2(const ll i, const ll j) { return (sum_2(j) - sum_2(i - 1) + M) % M; }
inline ll sum_3(const ll i, const ll j) { return (sum_3(j) - sum_3(i - 1) + M) % M; }

ll pow_f(ll b, ll e) {
    ll ans = 1;
    b = b % M;
    while (e) {
        if (e & 1) {
            ans = (ans * b) % M;
        }
        b = (b * b) % M;
        e >>= 1;
    }
    return ans;
}

ll nCr(ll n, ll r) {
    if (r > n || n < 0 || r < 0) {
        return 0;
    }
    if (n == r || r == 0) {
        return 1;
    }
    r = min(r, n - r);
    ll ans = 1;
    for (ll i = 1; i <= r; ++i) {
        ans = (ans * (n - i + 1)) / (i);
    }
    return ans;
}

ll nCr(tuple<ll, ll> t) {
    auto n = get<0>(t);
    auto k = get<1>(t);
    return nCr(n + k - 1, k);
}

template <typename T>
void print(T v) {
    cout << v << " ";
}

template <typename T>
void print(vector<T> v) {
    for (auto &i : v) {
        print(i);
    }
    cout << endl;
}

class Graph {
    struct edge_info {
        ll node_id;  // destination
        ll cost;     // Ai
        ll weight;   //Bi
    };

    struct node_info {
        ll silver_coin_num;  // Ci
        ll d;                // Di
    };

    struct set_info {
        ll city_id;
        ll silver_coin;
        ll time;
        bool operator>(const set_info &other) const {
            return (this->time > other.time) || (this->silver_coin > other.silver_coin) || (this->city_id > other.city_id);
        }
    };

    ll n, m;
    ll S;
    ll A_sum = 0;
    ll A_max = 0;
    vector<vector<edge_info>> adj;
    vector<node_info> city;
    vector<vector<ll>> DP;

   public:
    Graph(ll n, ll m, ll S) : n(n), m(m), S(S), adj(n + 1), city(n + 1) {}

    void addEdge(ll u, ll v, ll a, ll b) {
        adj[u].push_back({v, a, b});
        adj[v].push_back({u, a, b});
        A_max = max(A_max, a);
        A_sum += a; 
    }

    void addCityInfo(ll cityId, ll c, ll d) {
        city[cityId] = {c, d};
    }

    void dijkstra() {
        A_sum = min(A_sum, A_max*(n-1));
        DP.resize(n + 1, vector(A_sum + 1, INF));

        priority_queue<set_info, vector<set_info>, greater<set_info>> s;
        S = min(S, A_sum);
        s.push({1, S, 0});
        DP[1][S] = 0;

        while (!s.empty()) {
            auto top = s.top();
            s.pop();

            for (ll i = 0; i < top.silver_coin; ++i) {
                auto temp = top.time;
                if (temp < DP[top.city_id][i]) {
                    DP[top.city_id][i] = temp;
                    // s.push({top.city_id, i, temp});
                }
            }

            for (ll i = A_sum, prev = -1; i >= top.silver_coin + 1; --i) {
                auto temp = city[top.city_id].d * (ll)ceil((1.0 * i - top.silver_coin) / city[top.city_id].silver_coin_num);
                
                if (top.time + temp < DP[top.city_id][i]) {
                    DP[top.city_id][i] = top.time + temp;
                    if (prev != temp) {
                        s.push({top.city_id, i, top.time + temp});
                        prev = temp;
                    }
                }
            }

            for (auto &i : adj[top.city_id]) {
                if (i.cost <= top.silver_coin) {
                    if (DP[i.node_id][top.silver_coin - i.cost] >
                        DP[top.city_id][top.silver_coin] + i.weight) {
                        DP[i.node_id][top.silver_coin - i.cost] =
                            DP[top.city_id][top.silver_coin] + i.weight;
                        
                        s.push({i.node_id,
                                  top.silver_coin - i.cost,
                                  DP[i.node_id][top.silver_coin - i.cost]});
                    }
                }
            }
        }
        // print(DP);
        for (ll i = 2; i <= n; ++i) {
            cout << *min_element(DP[i].begin(), DP[i].end()) << endl;
        }
    }
};

void solve() {
    ll n, m, s;
    cin >> n >> m >> s;

    Graph g(n, m, s);
    for (int i = 0; i < m; ++i) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        g.addEdge(u, v, a, b);
    }
    
    for (int i = 0; i < n; ++i) {
        ll c, d;
        cin >> c >> d;
        g.addCityInfo(i + 1, c, d);
    }

    g.dijkstra();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef D_LOCAL
        freopen("in.in", "r", stdin);
        freopen("out.out", "w", stdout);
    #endif

    solve();

    return 0;
}

Measured memory_bytes: 7368