//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #ifdef ONLINE_JUDGE
        #pragma GCC target ("avx512f")
    #else
        #pragma GCC target ("avx")
    #endif
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

//--------------------------------------------

int n,m,s;
int u,v,a,b;
vpi city;
priority_queue<pair<pi,int>, vector<pair<pi,int>>, greater<pair<pi,int>>> state;
int silverbest[50][5001];

int SILVER_MAX = 0;
void update_silver(int pos, int silver, int tim){
    if (silver >= 5001) silver = SILVER_MAX;
    REP(i,silver+1) silverbest[pos][i] = min(silverbest[pos][i], tim);
}

signed main(){
    cin >> n >> m >> s;
    vvi disttable = vvi(n, vi(n, LONG_LONG_MAX/2));
    vvi cointable = vvi(n, vi(n, LONG_LONG_MAX/2));

    vi ret = vi(n, LONG_LONG_MAX/2);
    ret[0] = 0;
    REP(i,50) REP(j,5001) silverbest[i][j] = LONG_LONG_MAX/2;
    
    REP(i,m){
        cin >> u >> v >> a >> b;
        u--; v--;
        disttable[u][v] = b;
        disttable[v][u] = b;
        cointable[u][v] = a;
        cointable[v][u] = a;
        SILVER_MAX += a;
    }

    REP(i,n){
        cin >> a >> b;
        city.eb(a,b);
    }
    
    state.emplace(mp(0,s),0);
    while(!state.empty()){
        auto p = state.top();
        state.pop();
        int tim = p.first.first;
        int silv = p.first.second;
        int pos = p.second;
        // cerr << pos << " " << silv << " " << tim << endl;
        if (silv > SILVER_MAX) silv = SILVER_MAX;
        
        // if (silverbest[pos][silv] <= tim ) continue;
        update_silver(pos, silv, tim);

        REP(dest, n){
            if (cointable[pos][dest] > silv) continue;
            if (silverbest[dest][silv - cointable[pos][dest] ] <= tim + disttable[pos][dest])
                continue;
            state.emplace(mp(tim+disttable[pos][dest], silv-cointable[pos][dest]), dest);
            
        }
        while(silv < SILVER_MAX){
            tim += city[pos].second;
            silv += city[pos].first;
            if (silverbest[pos][silv] <= tim ) continue;
            update_silver(pos, silv, tim);
            state.emplace(mp(tim,silv), pos);
        }
    }

    FOR(i,1,n){
        cout << silverbest[i][0] << endl;
    }

    
}

Measured memory_bytes: 29700