#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  long long n,m,s;
  long long t=5000;
  cin >> n >> m >> s;
  vector<vector<long long>> k(n,vector<long long>(t));
  long long inf=100000000000000;
  rep(i,n){
    rep(j,t){
      k[i][j]=inf;
    }
  }
  vector<long long> u(n);
  vector<long long> v(n);
  vector<vector<long long>> uu(n,vector<long long>(n));
  vector<vector<long long>> vv(n,vector<long long>(n));
  rep(i,n){
    rep(z,n){
      uu[i][z]=0;
      vv[i][z]=0;
    }
  }
  vector<vector<long long>> w(n,vector<long long>(1,inf));
  //rep(i,n)w[i].pop_back();
  rep(i,m){
    long long a,b,c,d;
    cin >> a >> b >> c >> d;
    a--;
    b--;
    w[a].push_back(b);
    w[b].push_back(a);
    uu[a][b]=c;
    uu[b][a]=c;
    vv[a][b]=d;
    vv[b][a]=d;
  }
  rep(i,n){
    cin >> u[i];
    cin >> v[i];
  }
  vector<long long> o(n,0);
  rep(i,min(t,s+1)){
    k[0][i]=0;
  }
  while(true){
    long long b=-1;
    long long mi=inf/1000;
    rep(i,n){ 
      if(o.at(i)<t&&k.at(i).at(o.at(i))<mi){
        mi=k.at(i).at(o.at(i));
        b=i;
      }
    }
    if(b==-1)break;
    o.at(b)++;
    //if(o[b]%3==0||o[b]<10)cout << b << " " << o[b] << endl;
    for(long long h: w.at(b)){
      if(h>1000)continue;
      if(o.at(h)==t)continue;
      if(o.at(h)+uu.at(b).at(h)>=t)continue;
      if(o[b]-1-uu[b][h]>=0){
        k[h][o[b]-1-uu[b][h]]=min(k[h][o[b]-1-uu[b][h]],k[b][o[b]-1]+vv[b][h]);
        //cout << h << b  <<  " " << k[h][o[b]-1-uu[b][h]] << endl;
      }
      //else if(o[b]<20)cout << o[b] << " " << uu[b][h] << endl;
      //if(h==2&&b!=0)cout << h << " " << b << " " << k[h][o[h]] << " " << k[b][o[h]+uu[b][h]] << " " << vv[b][h] << endl;
    }
    long long y=0;
    long long p=max(y,o[b]-u[b]);
    if(o[b]>=t)continue;
    k[b][o[b]]=min(k[b][o[b]],k[b][p]+v[b]);
  }
  rep(i,n-1){
    cout << k[i+1][0] << endl;
  }
}
