#include <bits/stdc++.h>
using namespace std;
#define int long long
struct E{int to,co,ti;};
struct P{
  int tim,idx,res;
};
bool operator <(const P &a,const P &b){
  return a.tim<b.tim;
}
bool operator >(const P &a,const P &b){
  if(a.tim!=b.tim)return a.tim>b.tim;
  return a.res<b.res;
}

signed main(){
  int n,m,s;cin>>n>>m>>s;
  vector<E> edge[n];
  while(m--){
    int u,v,a,b;cin>>u>>v>>a>>b;u--;v--;
    edge[u].push_back({v,a,b});
    edge[v].push_back({u,a,b});
  }
  vector<int> c(n),d(n);
  for(int i=0;i<n;i++)cin>>c[i]>>d[i];
  priority_queue<P,vector<P>,greater<P>> que;
  vector<int> ans(n,-1);
  que.push({0,0,s});
  int cnt=0;
  while(que.size()){
    P p=que.top();que.pop();bool al=true;
    if(ans[p.idx]<0){
      al=false;
      ans[p.idx]=p.tim;
      if(++cnt==n)break;
    }
    do{
      for(auto q:edge[p.idx]){
        if(q.co>p.res)continue;
        que.push({p.tim+q.ti,q.to,p.res-q.co});
      }
      p.res+=c[p.idx];
      p.tim+=d[p.idx];
    }while(!al&&p.res<=5000);
  }
  for(int i=1;i<n;i++)cout<<ans[i]<<endl;
}
