#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = int_fast64_t;
using pll = pair<ll,ll>;
constexpr ll INF = 1LL<<60;
constexpr ll MOD = 1e9+7;
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
#if loc||local
void dump(){cerr<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);}
#else
void dump(){}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){}
#endif
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;}
template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;}
template<class T>vector<T> vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));}

struct edge{
  int to;
  ll a,b;
  edge(){}
  edge(int t,ll a,ll b):to(t),a(a),b(b){}
};

signed main(){

  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n,m,s;
  cin>>n>>m>>s;
  vector<vector<edge>> adj(n);
  auto cost_mat = vec<ll>(n,n);
  auto time_mat = vec<ll>(n,n);
  rep(i,m){
    ll u,v,a,b;
    cin>>u>>v>>a>>b;
    u--;v--;
    adj[u].emplace_back(v,a,b);
    adj[v].emplace_back(u,a,b);
    cost_mat[u][v] = cost_mat[v][u] = a;
    time_mat[u][v] = time_mat[v][u] = b;
  }
  vector<double> c(n),d(n);
  rep(i,n)cin>>c[i]>>d[i];

  vector<ll> ans(n,INF);

  auto my_find = [](auto& v,auto x)->bool{
    for(auto& vi:v)if(vi==x)return true;
    return false;
  };

  auto enum_path = [&](int t){
    queue<tuple<int,vector<int>,ll>> que;
    vector<int> asdf;
    que.emplace(0,asdf,0);
    vector<int> used(n);
    vector<pair<vector<int>,ll>> res;
    while(!que.empty()){
      auto [cur,prvs,cost] = que.front();
      que.pop();
      prvs.emplace_back(cur);
      if(cur==t){
        res.emplace_back(prvs,cost);
        continue;
      }
      for(auto nxt:adj[cur]){
        if(my_find(prvs,nxt.to))continue;
        que.emplace(nxt.to,prvs,cost+nxt.a);
      }
    }
    return res;
  };
  auto solve = [&](int t){
    auto candidate = enum_path(t);
    //for(auto elm:candidate)dump(elm.first,elm.second);
    for(auto [path,cost]:candidate){
      if(cost<=s){
        ll tmp = 0;
        rep(i,size(path)-1){
          tmp += time_mat[path[i]][path[i+1]];
        }
        chmin(ans[t],tmp);
        continue;
      }
      // ci/di
      double max_ef = c[0]/d[0];
      int max_ef_id = 0;
      ll silver = s;
      ll tmp = 0;
      rep(i,size(path)-1){
        if(chmax(max_ef,c[path[i]]/d[path[i]]))max_ef_id=path[i];
        auto& need_c = cost_mat[path[i]][path[i+1]];
        if(silver<need_c){
          ll nokori_c = need_c-silver;
          ll cnt = (nokori_c-1)/c[max_ef_id]+1;
          tmp += cnt*d[max_ef_id];
          silver += cnt*c[max_ef_id];
        }
        silver -= need_c;
        tmp += time_mat[path[i]][path[i+1]];
      }
      chmin(ans[t],tmp);
    }
  };

  for(int t=1;t<n;++t){
    solve(t);
  }

  for(int i=1;i<n;++i)cout<<ans[i]<<endl;


}