#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define mod ((int)1e9+7)
#define lim 1000000000000000007
#define lim1 18446744073709551615  //Unsigned
#define sq(a) ((a)*(a))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mms(v,i) memset(v,i,sizeof(v))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> PL;
typedef pair<ll,int> PLI;
typedef pair<int,ll> PIL;
typedef pair<ll,pair<int,int> > pii;
typedef pair<double,double> pdd;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a,ll b) {
   ll res=1;
   while(b){
      if(b%2==1) res=(res*a)%mod;
      a=(a*a)%mod;
      b>>=1;
   }
   return res;
}
ll gcdll(ll a,ll b) {
    if (b==0) return a;
    return gcdll(b,a%b);
}
int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = (int)2e5+5;
const int M = (int)3e3+5;
const int Q = 301;
const int logN = 19;

ll dp[55][2505];
vector<pii> v[55][2505];
void solve() {
    int n,m,s,x,y,a,b;
    cin>>n>>m>>s;
    int u = 2500;
    REP(i,1,n) {
        REP(j,0,u) {
            dp[i][j] = lim;
        }
    }
    REP(i,1,m) {
        cin>>x>>y>>a>>b;
        REP(j,a,u) {
            v[x][j].pb({b,{y,j-a}});
            v[y][j].pb({b,{x,j-a}});
        }
    }
    REP(i,1,n) {
        cin>>a>>b;
        REP(j,0,u-a) {
            v[i][j].pb({b,{i,j+a}});
        }
    }
    s = min(s,u);
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    dp[1][s] = 0;
    pq.push({dp[1][s],{1,s}});
    while(!pq.empty()) {
        pii temp = pq.top();
        pq.pop();
        if(temp.first>dp[temp.second.first][temp.second.second]) {
            continue;
        }
        for(auto it:v[temp.second.first][temp.second.second]) {
            if(it.first+temp.first<dp[it.second.first][it.second.second]) {
                dp[it.second.first][it.second.second] = it.first + temp.first;
                pq.push({dp[it.second.first][it.second.second],{it.second.first,it.second.second}});
            }
        }
    }
    REP(i,2,n) {
        ll ans = lim;
        REP(j,0,u) {
            ans = min(ans,dp[i][j]);
        }
        cout<<ans<<"\n";
    }
}
int main() {
    //freopen("output.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T=1;
    //cin>>T;
    REP(TC,1,T) {
        //cout<<"Case #"<<TC<<": ";
        solve();
        //cout<<"\n";
    }
}


Measured memory_bytes: 24040