#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 5e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//
template <typename T>
struct dijkstra{
    using P = pair<T, ll>;
    const T inf = numeric_limits<T>::max();
    vector<vector<pair<ll,T>>> G;
    vector<ll> beforev;
    vector<T> dist;
    ll N, start;
    priority_queue<P, vector<P>, greater<P>> pq;

    dijkstra(ll n) : N(n) {
        G.resize(n), beforev.assign(n, -1), dist.assign(n, inf);
    }

    void add_edge(ll u, ll v, T cost){
        G[u].emplace_back(v, cost);
    }

    void init(ll s){
        start = s;
        fill(beforev.begin(), beforev.end(), -1), fill(dist.begin(), dist.end(), inf);
        dist[start] = 0, pq.emplace(0, start);
        
        while(!pq.empty()){
            T c; ll from;
            tie(c, from) = pq.top(), pq.pop();
            if (dist[from] < c) continue;
            for(auto& e: G[from]){
                ll to; T cost;
                tie(to, cost) = e;
                if(dist[to]>dist[from]+cost){
                    dist[to] = dist[from] + cost;
                    beforev[to] = from;
                    pq.emplace(dist[to], to);
                }
            }
        }
    }

    vector<ll> get_route(ll goal){
        vector<ll> route;
        ll now = goal;
        while(now!=-1){
            route.emplace_back(now);
            now = beforev[now];
        }
        reverse(route.begin(), route.end());
        return route;
    }
};
const ll MS = 2500;
int main() {
    init();
    ll N, M, S;
    cin >> N >> M >> S;
    dijkstra<ll> D(N * MS);
    chmin(S, MS - 1);
    rep(i,M){
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        rep(j,MS-a){
            D.add_edge(u * MS + j + a, v * MS + j, b);
            D.add_edge(v * MS + j + a, u * MS + j, b);
        }
    }
    rep(i,N){
        ll c, d;
        cin >> c >> d;
        rep(j,MS-c){
            D.add_edge(i * MS + j, i * MS + j + c, d);
        }
    }

    D.init(S);

    repe(i,1,N){
        ll ans = INF;
        rep(j, MS) chmin(ans, D.dist[i * MS + j]);
        cout << ans << endl;
    }
}

Measured memory_bytes: 24792