#include<stdio.h>
long long MIN(long long a,long long b){return a<b?a:b;}
long long R=1,C=1,H[2000010],N[2000010];
//評価関数（いまはMIN）
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]<N[H[b]]?1:0;
}
//挿入関数
void hin(long long a){
  //if(C==1)R=1;
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
//取り出す関数
int hout(){
  int rt=H[1],i,j=2,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[j/2]=k;
  return rt;
}
long long ta[60],to[300],nt[300],co[300],ti[300],i,j,g[1000010],p[1000010];
int main(){
  long long n,m,a,b,c,d,e[60],f[60],dp[3000][60],ng,gi,po,s;
  for(i=0;i<3000;i++){
    for(j=0;j<60;j++)dp[i][j]=1e18;
  }
  for(i=0;i<60;i++)ta[i]=-1;
  scanf("%lld %lld %lld",&n,&m,&s);
  s=MIN(s,2500);
  for(i=0;i<m;i++){
    scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
    nt[i  ]=ta[to[i+m]=a];
    nt[m+i]=ta[to[i  ]=b];
    ti[i]=ti[i+m]=d;
    co[ta[a]=i]=co[ta[b]=i+m]=c;
  }
  for(i=0;i<n;i++)scanf("%lld %lld",&e[i+1],&f[i+1]);
  //for(i=0;i<n;i++)printf("e:%lld ",e[i+1]);printf("\n");
  hin(dp[g[R]=s][p[R]=1]=0);
  while(C-1){
    i=hout();
    po=p[i];
    gi=g[i];//printf("!%lld %lld %lld \n",po,gi,N[i]);
    ng=MIN(gi+e[po],2500);//printf("%lld %lld %lld\n",dp[ng][po],N[i]+f[po],ng);
    if(dp[ng][po]>N[i]+f[po]){//printf("%lld\n",R);
      hin(dp[g[R]=ng][p[R]=po]=N[i]+f[po]);//printf("!!!%lld\n",R);
    }
    if(gi&&dp[gi-1][po]>N[i])hin(dp[g[R]=gi-1][p[R]=po]=N[i]);//printf("%lld\n",C);
    for(j=ta[po];j+1;j=nt[j]){//printf("::::%lld %lld %lld\n",gi,to[j],co[j]);
      if(gi<co[j])continue;
      if(dp[gi-co[j]][to[j]]>N[i]+ti[j])hin(dp[g[R]=gi-co[j]][p[R]=to[j]]=N[i]+ti[j]);
    }
  }
  for(i=2;i<=n;i++)printf("%lld\n",dp[0][i]);
  return 0;
}
  
     
