#include<queue>
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> P;
struct edge{
    ll to;
    ll cost;
    ll en;
    edge(ll t, ll w,ll e) : to(t), cost(w) ,en(e){ }
};
int main(){
  vector<vector<edge> > g(60);
  long long i,j,n,m,s,u,V,a,b,c[60],d[60];
  long long ds[60][3010],ns[60][3010];
  const long long INF=1000000000000000;
  priority_queue<P,vector<P>,greater<P> > que;
  scanf("%lld %lld %lld\n",&n,&m,&s);
  for(i=0;i<m;i++){
    scanf("%lld %lld %lld %lld\n",&u,&V,&a,&b);
    u--,V--;
    g[u].push_back(edge(V,b,a));
    g[V].push_back(edge(u,b,a));
  }
  for(i=0;i<n;i++){
    scanf("%lld %lld\n",&c[i],&d[i]);
  }
  for(i=0;i<n;i++){
    for(j=0;j<3000;j++){
      ds[i][j]=INF,ns[i][j]=0;
    }
  }
  if(s>2800){
    s=2800;
  }
  ds[0][s]=0,ns[0][s]=1;
  que.push(make_pair(0,pll(0,s)));
  while(!que.empty()){
    P p=que.top();
    ll v=p.second.first,w=p.second.second;
    que.pop();
    for(i=0;i<g[v].size();i++){
      edge us=g[v][i];
      if(ds[us.to][w-us.en]>ds[v][w]+us.cost && ns[us.to][w-us.en]==0 && w-us.en>=0){
        ds[us.to][w-us.en]=ds[v][w]+us.cost;
        que.push(make_pair(ds[us.to][w-us.en],pll(us.to,w-us.en)));
      }
      if(ds[v][w+c[v]]>ds[v][w]+d[v] && ns[v][w+c[v]]==0){
        ds[v][w+c[v]]=ds[v][w]+d[v];
        que.push(make_pair(ds[v][w+c[v]],pll(v,w+c[v])));
      }
    }
    ns[v][w]=1;
  }
  for(i=1;i<n;i++){
    ll min=INF;
    for(j=0;j<3000;j++){
      if(min>ds[i][j]){
        min=ds[i][j];
      }
    }
    printf("%lld\n",min);
  }
  return 0;
}