//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
#define endn "\n"
typedef pair<int,int> P;
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;}
const int MOD = 1000000007;
//const int MOD = 998244353;
template<class T> inline int add(T& a, T b, T M = MOD){a=(a+M)%M;b=(b+M)%M;a=(a+b)%M;return a;};
template<class T> inline int mul(T& a, T b, T M = MOD){if(a>=M)a%=M;if(b>=M)b%=M;a*=b;if(a>=M)a%=M;return a;};
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

////////////////////////////////////////////////////////////////////
///////////////////////___modpow___////////////////////
ll modpow(ll a,  ll n, const ll &MOD = MOD){
  ll ret = n == 0 ? 1 : modpow(a, n/2, MOD);
  (ret *= ret) %= MOD;
  if(n%2)((ret *= a) %= MOD);
  return ret;
}
///////////////////////___modinv___////////////////////
ll modinv(ll d, const ll &MOD = MOD){
  return modpow(d, MOD-2, MOD);
}
///////////////////////___combination___////////////////////
vector<ll> fac, finv, inv;
void COMinit(const int MAX = 5000000, const ll &MOD = MOD){
  fac.resize(MAX);finv.resize(MAX);inv.resize(MAX);
  fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;
  repd(i,2,MAX){
    fac[i] = fac[i-1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
    finv[i] = finv[i-1] * inv[i] % MOD;
  }
}
ll COM(int n, int k){
  if(n < k)return 0;
  if(n < 0 || k < 0)return 0;
  return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}
///////////////////////___inPrime___////////////////////
bool isPrime(int n){
  for(int i = 2;i*i <= n;i++){
    if(n % i == 0)return false;
  }
  return n != 1;
}

///////////////////////___divisor___////////////////////
vector<int> divisor(int n){
  vector<int> ret;
  for(int i = 1;i*i <= n;i++){
    if(n % i == 0){
      ret.push_back(i);
      if(n/i != i)ret.push_back(n/i);
    }
  }
  sort(ret.begin(), ret.end());
  return ret;
}

///////////////////////___prime_factor___////////////////////
map<int, int> prime_factor(int n){
  map<int, int> ret;
  for(int i = 2;i*i <= n;i++){
    while(n % i == 0){
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1){
    ret[n] = 1;
  }
  return ret;
}

///////////////////////___sieve___////////////////////////////
set<int> sieve(int n){
  set<int> primes;vector<bool> is_prime(n+1, true);
  is_prime[0] = is_prime[1] = false;
  repd(i, 2, n+1){
    if(is_prime[i]){
      primes.insert(i);
      for(int j = i*2;j <= n;j += i)is_prime[j] = false;
    }
  }
  return primes;
}

/////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////
int n,m,s;
const int MAX = 2500;
typedef pair<int, P> PP;
int dist[60][MAX+2], cc[60],dd[60];
vector<PP> g[60];
vector<int> ans;
signed main() {
  cin>>n>>m>>s;
  rep(i,m){
    int u,v,a,b;cin>>u>>v>>a>>b;u--;v--;
    g[u].push_back(PP(v,P(a,b)));
    g[v].push_back(PP(u,P(a,b)));
  }
  rep(i,n){
    cin>>cc[i]>>dd[i];
  }
  if(s > MAX)s = MAX+1;
  priority_queue<PP, vector<PP>, greater<PP>> que;
  rep(i,n)rep(j,MAX+2)dist[i][j] = INF;
  dist[0][s] = 0;
  que.push(PP(0,P(0,s)));
  while(!que.empty()){
    PP p = que.top();que.pop();
    int v = p.second.first, m = p.second.second;
    if(dist[v][m] < p.first)continue;
    rep(i, g[v].size()){
      int to = g[v][i].first, money = g[v][i].second.first, time = g[v][i].second.second;
      int to_money = (m == MAX+1 ? MAX+1 : m-money);
      if(m >= money && dist[to][to_money] > dist[v][m] + time){
        dist[to][to_money] = dist[v][m] + time;
        que.push(PP(dist[to][to_money], P(to, to_money)));
      }
    }
    int money = m + cc[v], time = dist[v][m] + dd[v];
    while(money <= MAX){
      if(dist[v][money] > time){
        dist[v][money] = time;
        que.push(PP(dist[v][money], P(v, money)));
      }
      money += cc[v];time += dd[v];
    }
    if(dist[v][MAX+1] > time){
      dist[v][MAX+1] = time;
      que.push(PP(dist[v][MAX+1], P(v, MAX+1)));
    }
  }
  ans = vector<int>(n, INF);
  repd(i,1,n){
    rep(j,MAX+2)chmin(ans[i], dist[i][j]);
  }
  repd(i,1,n){
    cout << ans[i] << endl;
  }
}



Measured memory_bytes: 101780