bool DBG = false;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_dec_float.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using ll = long long;
using ld = long double;
//using i128 = __int128_t;
//using bint = boost::multiprecision::cpp_int
//using d1024 = boost::multiprecision::number<mp::cpp_dec_float<1024>>;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define IFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define RPT(i,a,b) for(int i=(a);i<((a)+(b));++i)
#define IRPT(i,a,b) for(int i=((a)+(b)-1);i>=(a);--i)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define fs first
#define sd second
#define couts(x) cout << (x) << (" ")
#define coutn(x) cout << (x) << ("\n")
#define dcouts(x) if(DBG) couts(x)
#define dcoutn(x) if(DBG) coutn(x)
#define endl "\n"
#define psb push_back
#define ppb pop_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define LBIT(x,a) (((x)>>(a))&1LL)
#define IBIT(x,a) (((x)>>(a))&1)
#define BCOUNT(x) (__builtin_popcount(x))
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T1, typename T2> std::istream &operator>>(std::istream &is, std::pair<T1,T2> &p){is >> p.first >> p.second; return is; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::deque<T> &vec){ os << "deque["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> std::ostream &operator<<(std::ostream &os, const std::unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> std::ostream &operator<<(std::ostream &os, const std::map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> std::ostream &operator<<(std::ostream &os, const std::unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }

template<class T> using V = vector<T>;
template<class T> using V2 = V<V<T>>;
template<class T> using V3 = V<V2<T>>;
template<class T> using V4 = V<V3<T>>;


constexpr ll LINF = 1LL << 55;
using PL = pair<ll,ll>;
int n, m, scoin;ll comax=-1;
struct edge{
  ll time, money; int to;
  edge(){}
  edge(int a, ll b, ll c){ to = a, money = b, time = c;}
};
V2<edge> g;
V<PL> vp;
V2<ll> dist;

void dkj(int s=0){
  priority_queue< pair<PL,int>,
    V<pair<PL,int>>,
    greater<pair<PL,int>> >  q;
  dist[0][scoin] = 0;
  q.push(pair<PL,int>(PL(0, scoin), s));
  
  while(!q.empty()){
    auto p = q.top(); q.pop(); //couts(p);
    ll v_money = p.fs.sd, v_time = p.fs.fs;
    int v = (int)p.sd;
    if(dist[v][v_money] < v_time) continue;
    {
      ll nmoney = min<ll>(v_money + vp[v].fs, comax),ntime = v_time + vp[v].sd;
      if(ntime<dist[v][nmoney]){
        dist[v][nmoney] = ntime;
        q.push( make_pair(PL(ntime, nmoney), v) );
      }
    }
    for(auto x: g[v]){
      ll time = x.time, money = x.money; int to = x.to;
      time += v_time;
      money = v_money - money;
      if(money<0) continue;
      money = min(money, comax);
      if(time < dist[to][money]){
        dist[to][money] = time;
        q.push(  make_pair( PL(time, money ), to ));
      }
    }

  }
}



void solve(){
  cin >> n >> m >> scoin;
  g = V2<edge>(n);
  vp = V<PL>(n);
  FOR(i,0,m){
    int u, v; ll a, b;
    cin >> u >> v >> a >>  b;
    --u, --v;
    comax = max(comax, a);
    g[u].eb(v,a,b); 
    g[v].eb(u,a,b);
  }
  cin >> vp;
  comax *= n;
  dist = V2<ll>(n, V<ll>(comax+10, LINF));
  scoin = min<ll>(scoin, comax+2);
  dkj(0);
  FOR(i,1,n){
    ll ans = *min_element(dist[i].begin(), dist[i].begin()+comax+5);
    coutn(ans);
  }
  //coutn(dist);
  
}

int main(void){
  //std::cout << std::fixed << std::setprecision(20);
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}



Measured memory_bytes: 7200