#include "bits/stdc++.h"
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

ll n,m,s;
struct edge{/*重み付き,有向*/
    int to , cost;/*toは接続先*/
    edge(ll to_ ,ll cost_ = 1){ to=to_; cost=cost_; };/*全てのcost=1 <=> 無向グラフ*/
};
bool operator<(edge e1 ,edge e2){return e1.cost < e2.cost; }
bool operator>(edge e1 ,edge e2){return e1.cost > e2.cost; }
using graph =  vector< vector<edge> >;
graph g;

Vi c,d;

ll ca(ll id,ll cos){
    return id*(2501)+cos;
}

Vi dijkstra(graph _g,ll start){
    Vi dist; //for dijkstra. distance from start
    dist.resize(_g.size()); dist.resize(_g.size());
    rep(i,dist.size())dist[i]=INF;
    auto comp_pq = [](pair<ll,ll> x,pair<ll,ll> y){return x.second > y.second;};
    priority_queue< pair<ll,ll> , vector<pair<ll,ll>>, decltype(comp_pq)> pq{comp_pq};
    dist[start]=0; pq.push(mp(start,0));
    while (pq.size()>0){
        PLL p = pq.top();
        pq.pop();
        if(p.second > dist[p.first])continue;
        rep(i,_g[p.first].size()){
            if(dist[p.first]!=INF){
                if(chmin(dist[_g[p.first][i].to],dist[p.first]+_g[p.first][i].cost)){
                    pq.push(mp(_g[p.first][i].to,dist[_g[p.first][i].to]));
                }
            }
        }
    }
    return dist;
}

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    cin>>n>>m>>s;
    chmin(s,2500LL);
    ll uu,vv,aa,bb;
    g.resize(n*2501);
    rep(i,m){
        cin>>uu>>vv>>aa>>bb;
        uu--;
        vv--;
        rep(j,2501){
            if(j>=aa)g[ca(uu,j)].pb(edge(ca(vv,j-aa),bb));
            if(j>=aa)g[ca(vv,j)].pb(edge(ca(uu,j-aa),bb));
        }
    }
    c.resize(n);
    d.resize(n);
    rep(i,n){
        cin>>c[i]>>d[i];
    }
    rep(i,n){
        rep(j,2501){
            if(j+c[i]>=2501)break;
            g[ca(i,j)].pb(edge(ca(i,j+c[i]),d[i]));
        }
    }
    Vi dis = dijkstra(g,ca(0,s));
    rep(i,n){
        if(i==0)continue;
        ll ans = INF;
        rep(j,2501){
            chmin(ans,dis[ca(i,j)]);
        }
        print(ans);
    }
    return 0;
}

Measured memory_bytes: 26484