#line 1 "solve.cpp"
/*{{{*/
#ifndef HEADER_H
#define HEADER_H

// template version 2.0
using namespace std;
#include <bits/stdc++.h>

// varibable settings
#define int long long
const int INF = 1e18;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define _rrep(i, n) rrepi(i, 0, n)
#define rrepi(i, a, b) for (int i = (int)((b)-1); i >= (int)(a); --i)
#define r_rep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__)
#define each(i, a) for (auto &&i : a)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
#define ub upper_bound
#define lb lower_bound
#define lpos(A, x) (lower_bound(all(A), x) - A.begin())
#define upos(A, x) (upper_bound(all(A), x) - A.begin())
template <class T>
inline void chmax(T &a, const T &b) {
    if ((a) < (b)) (a) = (b);
}
template <class T>
inline void chmin(T &a, const T &b) {
    if ((a) > (b)) (a) = (b);
}

#define divceil(a, b) ((a) + (b)-1) / (b)
#define is_in(x, a, b) ((a) <= (x) && (x) < (b))
#define uni(x)    \
    sort(all(x)); \
    x.erase(unique(all(x)), x.end())
#define slice(l, r) substr(l, r - l)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int, int> pii;
typedef tuple<int, int, int> iii;

template <typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast() { std::cin.tie(0); ios::sync_with_stdio(false); } } fast;
void check_input(){
    assert(cin.eof() == 0);
    int tmp; cin >> tmp; 
    assert(cin.eof() == 1);
}

#if defined(PCM) || defined(LOCAL)
#else
#define dump(...) ;
#define dump_1d(...) ;
#define dump_2d(...) ;
#define cerrendl ;
#endif

#endif /* HEADER_H *//*}}}*/


// this module is depricated. use graph.hpp
using Pos = int;  // TODO: update if needed

using Cost = int;     // TODO: update if needed
Cost zerocost = 0LL;  // TODO: update if needed
Cost infcost = INF;   // TODO: update if needed

struct Edge {
    Pos to; /*{{{*/
    Cost cost;
    Edge(Pos to, Cost cost) : to(to), cost(cost) {}
    friend auto& operator<<(auto& os, const Edge& e) {
        os << e.to << " " << e.cost;
        return os;
    } /*}}}*/
};
struct Graph {
    unordered_map<Pos, vector<Edge>>
        all_edges;  // Posがpiiでなくintならunordredの方が早い{{{
    void add_edge(Pos from, Pos to, Cost cost) {
        all_edges[from].emplace_back(to, cost);
    }

    auto operator[](Pos pos) { return all_edges[pos]; }

    friend auto& operator<<(auto& os, const Graph& G) {
        os << G.all_edges;
        return os;
    } /*}}}*/
};
struct Dist {
    unordered_map<Pos, Cost> data; /*{{{*/
    Cost operator[](Pos pos) {
        if (data.find(pos) != data.end())
            return data[pos];
        else
            return infcost;
    } /*}}}*/
};
Dist dijkstra(Graph& G, vector<Pos> starts) {  // 多点スタート
    Dist d;                                    // 最短距離{{{
    PQ<pair<Cost, Pos>> pq;
    each(start, starts) {
        d.data[start] = zerocost;
        pq.push(mp(zerocost, start));
    }
    while (!pq.empty()) {
        auto cp = pq.top();
        pq.pop();
        auto cost = cp.first;
        auto u = cp.second;
        for (const auto& edge : G[u]) {
            Pos v = edge.to;
            Cost ncost = cost + edge.cost;
            if (ncost < d[v]) {
                d.data[v] = ncost;
                pq.push(mp(ncost, v));
            }
        }
    }
    return d; /*}}}*/
};
Dist dijkstra(Graph& G, Pos start) {
    vector<Pos> starts = {start};
    return dijkstra(G, starts);
};
signed main() {
    //input
    int n,m,s;cin>>n>>m>>s;/*{{{*/
    chmin(s, 2500LL);
    int cnt = 0;
    Graph G;
    vi u(m), v(m), a(m), b(m);
    auto f = [&](int u, int r){
        return 2501*u + r;
    };
    rep(i, m){
        cin>>u[i]>>v[i]>>a[i]>>b[i];
        u[i]--;v[i]--;
        rep(r, 0, 2501){
            if (r-a[i]>=0) G.add_edge(f(u[i], r), f(v[i], r-a[i]), b[i]), cnt++;
            if (r-a[i]>=0) G.add_edge(f(v[i], r), f(u[i], r-a[i]), b[i]), cnt++;
        }
    }
    dump(u);
    dump(v);
    dump(a);
    dump(b);
    dump(s);

    vi c(n), d(n);
    rep(i, n){
        cin>>c[i]>>d[i];
        rep(r, 0, 2501){
            if (r+c[i]<2501) G.add_edge(f(i, r), f(i, r+c[i]), d[i]), cnt++;
        }
    }
    dump(c);
    dump(d);
    dump(cnt);
    check_input();/*}}}*/

    // calc min distance by G
    auto dist = dijkstra(G, f(0, s));
    rep(i, 1, n){
        int ans = INF;
        rep(r, 0, 2501) chmin(ans, dist[f(i, r)]);
        cout << ans << endl;
    }

    return 0; 
}


Measured memory_bytes: 30880