#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

template<typename T>
inline void scan(std::deque<T>&v){for(auto&& sv:v){scan(sv);}}

using namespace std;

int silver_max = 2500;
struct Edge {
  ll to, silver, time;
};
struct State {
  ll min_time, node, silver;
};

ll INF = 1e16;
ll n;
vi c, d;

vector<vector<Edge> > g; // 隣接リスト
vvll dist;

void dijkstra(int s) {
  dist.assign(n, vll(silver_max+1, INF));
  priority_queue<vll, vector<vll>, greater<vll> > q;
  s = min(s, silver_max);
  dist[0][s] = 0;
  q.push(vll{0, 0, s});
  while (!q.empty()) {
    auto state = q.top();
    //debug(state);
    q.pop();
    int v = state[1];
    if (state[0] > dist[v][state[2]]) {
      continue;
    }
    ll next_silver, next_time;
    //debug2(v, g[v].size());
    for (auto edge : g[v]) {
      //debug3(edge.to, edge.silver, edge.time);
      next_silver = state[2] - edge.silver;
      if (next_silver >= 0) {
        next_time = state[0] + edge.time;
        if (dist[edge.to][next_silver] > next_time) {
          dist[edge.to][next_silver] = next_time;
          q.push(vll{next_time, edge.to, next_silver});
        }
      }
    }
    if (state[2] >= silver_max) {
      continue;
    }
    next_time = state[0] + d[v];
    next_silver = min((ll)silver_max, state[2] + c[v]);
    if (next_time < dist[v][next_silver]) {
      dist[v][next_silver] = next_time;
      q.push(vll{next_time, v, next_silver});
    }
  }
}

void solve() {
  ll m, s;
  scan(n, m, s);
  g.resize(n);
  rep (i, m) {
    int u, v, a, b;
    scan(u, v, a, b);
    --u;
    --v;
    g[u].push_back(Edge{v, a, b});
    g[v].push_back(Edge{u, a, b});
  }
  c.resize(n);
  d.resize(n);
  rep (i, n) {
    scan(c[i], d[i]);
  }
  dijkstra(s);
  //debug(dist);
  FOR (i, 1, n) {
    ll ans = INF;
    rep (j, silver_max+1) {
      ans = min(ans, dist[i][j]);
    }
    print(ans);
  }
}

int main() {
  solve();
  return 0;
}


Measured memory_bytes: 8900