#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;
}
int ans[50][5001];
const long long LINF=1e18;
template<typename T>
void chmin(T &a,T b){
  if(a>b)a=b;
}

signed main(){
  memset(ans,-1,sizeof(ans));
  int n,m,s;cin>>n>>m>>s;chmin(s,5000LL);
  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;
  que.push({0,0,s});
  vector<int> fans(n,-1);
  int cnt=0;
  while(que.size()){
    P p=que.top();que.pop();//cout<<p.idx<<" "<<p.res<<" "<<p.tim<<" "<<cnt<<endl;
    if(~ans[p.idx][p.res])continue;
    ans[p.idx][p.res]=p.tim;
    if(fans[p.idx]<0){
      fans[p.idx]=p.tim;
      if(++cnt==n)break;
    }
    do{
      for(auto q:edge[p.idx]){
        if(p.res<q.co||~ans[q.to][p.res-q.co])continue;
        que.push({p.tim+q.ti,q.to,p.res-q.co});
      }
      p.res+=c[p.idx];
      p.tim+=d[p.idx];
    }while(p.res<5000);
  }
  for(int i=1;i<n;i++)cout<<fans[i]<<endl;
}
