#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 30)
#define MOD 1000000007
//int dy[4] = {-1,0,0,1};
//int dx[4] = {0,1,-1,0};

struct edge{
  int to,s,t;
  bool operator<(const edge &other)const{
    return t > other.t;
  }
};

int main(){
  
  int n,m,S;
  cin >> n >> m >> S;
  const int max_S = 5000;
  S = min(max_S,S);
  vector<vector<edge>> v(n);
  REP(i,m){
    int fr,to,a,b;cin >> fr >> to >> a >> b;
    fr--,to--;
    v[fr].push_back({to,a,b});
    v[to].push_back({fr,a,b});
  }
  vector<P> cost(n);
  REP(i,n)cin >> cost[i].first >> cost[i].second;
  priority_queue<edge> que;
  que.push({0,S,0});
  vector<vector<int>> dist(n,vector<int>(5001,INF));
  dist[0][S] = 0;
  auto push = [&](edge vv,edge vvv){
    if(vv.s < vvv.s)return ;
    int ns = min(vv.s-vvv.s,max_S);
    if(dist[vvv.to][ns] <= dist[vv.to][vv.s]+vvv.t)return ; 
    dist[vvv.to][ns] = dist[vv.to][vv.s]+vvv.t;
    que.push({vvv.to,ns,dist[vvv.to][ns]});
  };
  while(!que.empty()){
    edge e = que.top();que.pop();
    if(dist[e.to][e.s] != e.t)continue;
    push(e,{e.to,-cost[e.to].first,cost[e.to].second});
    for(auto nv : v[e.to])push(e,nv);
  }
  for(int i = 1;i < n;i++){
    ll res = INF;
    REP(j,5001)res = min(res,1ll*dist[i][j]);
    cout << res << endl;
  }



  

  return 0;
}