// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << " = " << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define SP << " " <<

typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<ll,vector<ll>,greater<ll>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;

const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const int INF = (1LL << 60); // 1152921504606846976
const double EPS = (1 >> 30);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> inline T ceil(T a, T b) {return T((a + b - 1) / b);}
template<class T> inline T round(T a, T b) {return T(a / b);}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
template <class T> inline void out(T &a) { bool flag=true; for(auto&x:a){if(flag) {flag=false;} else{ cout << ' '; } cout<<x; } cout << endl; }



//----------------------------------------------------------------
int nmax=200000; // 2*(10^5)
vvec g(nmax);


struct edge{
    int to,a,b;
};


void solve4ts()
{
    
    int n,m,s;
    cin>>n>>m>>s;
    vector<vector<edge>> g(n);
    rep(i,m){
        int u,v,a,b;
        cin>>u>>v>>a>>b;
        --u;--v;
        g[u].pb({v,a,b});
        g[v].pb({u,a,b});
    }
    vec c(n),d(n);
    rep(i,n) cin>>c[i]>>d[i];
    priority_queue<pair<int,P>, vector<pair<int,P>>, greater<pair<int,P>>> Q;
    vvec dist(55,vec(2520,INF));
    if(s>=2500) s=2500;
    dist[0][s]=0;
    Q.push(make_pair(0,P(0,s)));
    while(!Q.empty()){
        pair<int,P> p=Q.top(); Q.pop();
        int v=p.sc.fs,sil=p.sc.sc,di=p.fs;
        if(di>dist[v][sil]) continue;
        if(sil<2500){
            int nsil=sil+c[v];
            if(nsil>2500) nsil=2500;
            if(chmin(dist[v][nsil],di+d[v])){
                Q.push(make_pair(di+d[v],P(v,nsil)));
            }
        }
        for(auto e:g[v]){
            int to=e.to;
            int a=e.a;
            int b=e.b;
            if(sil>=a){
                if(chmin(dist[to][sil-a],di+b)){
                    Q.push(make_pair(di+b,P(to,sil-a)) );
                }
            }
        }
    }
    for(int i=1;i<n;i++){
        int ans=INF;
        rep(j,2501){
            chmin(ans,dist[i][j]);
        }
        cout<<ans<<endl;
    }
}
//-----------------------------------------------------------------

signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15);
    int repeat = 1;
    // cin >> repeat;
    while(repeat--) solve4ts();
}

Measured memory_bytes: 12192