// // If you want something you've never had, you must be willing to do
// // something you've never done

// //  When the going gets tough,  the tough get going

// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<pair<int,int>, null_type,less<pair<int, int> >,rb_tree_tag,tree_order_statistics_node_update > pbds;

#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#define ROUNDOFFINT(d) d = (int)((double)d + 0.5)
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define pb push_back
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// #define int ll
ll power(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    while(b) {
        if(b % 2) {
            res *= a;
            res %= mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res % mod;
}
const int INF = 2e9;

// ----------------------------------------------------------
#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, s;
int c[55], d[55];
vector<pair<int, pair<int,int> > > g[52];
int sol[55], dist[52][2455];

void dijkstra() {
    for(int i=0; i<=52; i++) sol[i] = 2e18;
    for(int i=0; i<52; i++) {
        for(int j=0; j<2455; j++) {
            if(i == 1 && j == s) continue;
            dist[i][j] = 2e18;
        }
    }
    set<pair<int, pair<int,int> > > st;
    if(s > 2450) s = 2450;
    st.insert({0, {1, s}});
    while(!st.empty()) {
        auto it = st.begin();
        int i = (*it).second.first;
        // debug(i);
        int coin = (*it).second.second;
        assert(coin >= 0);
        int dd = it->first;
        // debug3(i, coin, dd);
        st.erase(it);
        for(auto it: g[i]) {
            int paise = it.second.first, time = it.second.second;
            int v = it.first;
            if(coin >= paise) {
                if(dd + time < dist[v][coin - paise]) {
                    dist[v][coin - paise] = dd + time;
                    st.insert({dd+time, {v, coin - paise}});
                }
            }
        }
        if(dd + d[i] < dist[i][min(2450*1LL, c[i] + coin)]) {
            dist[i][min(2450*1LL, c[i] + coin)] = dd + d[i];
            st.insert({dd + d[i], {i, min(2450*1LL, c[i] + coin)}});
        }
    }
    for(int i=2; i<=n; i++) {
        for(int j=0; j<=2450; j++) {
            sol[i] = min(sol[i], dist[i][j]);
        }
    }
}

signed main() {
    cin >> n >> m >> s;
    for(int i=1, u, v, a, b; i<=m; i++) {
        cin >> u >> v >> a >> b;
        g[u].pb({v, {a, b}});
        g[v].pb({u, {a, b}});
    }
    for(int i=1; i<=n; i++) cin >> c[i] >> d[i];
    dijkstra();
    for(int i=2; i<=n; i++) cout << sol[i] << '\n';
    return 0;
}


Measured memory_bytes: 9140