#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using VI=vector<ll>;
using VD=vector<ld>;
using VVI=vector<VI>;
using VC=vector<char>;
using VVC=vector<VC>;
using VS=vector<string>;
using PLL =pair<ll,ll>;
using PLD=pair<ld,ld>;
using VPLL=vector<PLL>;
#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 FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element((x).begin(),(x).end())
#define MIN(x) *min_element((x).begin(),(x).end())
#define SORTR(x) sort((x).rbegin(),(x).rend())
#define SORT(x) sort((x).begin(),(x).end())
#define SUM(x) accumulate((x).begin(),(x).end(), (ll)0)
#define FILL(x,a) fill(x.begin(),x.end(),a)
#define EACH(i,x) for(typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)

const int INF  = 1<<30;
const ld EPS   = 1e-10;
const int MOD  = int(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 (b<a) { a=b; return 1; } return 0; }
template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last){reverse(middle, last); return next_permutation(first , last);}
#define COUT(x) cout<<x<<"\n"

class Dijkstra{
 private:
  struct edge{
	ll to;
	ll cost;
  };
  vector<vector<edge>> G;
  vector<ll> d;
  ll siz;
 public:
  Dijkstra(ll n){
	  G.resize(n);
	  siz = n;
  }
  void add_edge(ll from,ll to,ll cost){
	  G[from].push_back(edge{to,cost});
  }
  vector<ll> dijkstra(ll s){
	  priority_queue<PLL,vector<PLL>,greater<PLL>> pq;
	  d.assign(siz,INF);
	  d[s] = 0;
	  pq.push(PLL(0,s));
	  while(!pq.empty()){
		  PLL p = pq.top();pq.pop();
		  ll v = p.second;
		  if (d[v] < p.first) continue;
		  for(edge &e:G[v]){
			  if (chmin(d[e.to],d[v]+e.cost)){
				  pq.push(PLL(d[e.to],e.to));
			  }
		  }
	  }
	  return d;
  }
};
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
void Main()
{
  ll n,m,s;
  cin >> n >> m >> s;
  Dijkstra g(2501*n); // u:2500*u+money
  ll u,v,a,b,c,d;
  REP(i,m){
    cin >> u >> v >> a >> b;
    --u;
    --v;
    rep(i,a,2501){
      g.add_edge(2501*u+i,2501*v+i-a,b);
      g.add_edge(2501*v+i,2501*u+i-a,b);
    }
  }
  rep(i,n){
    cin >> c >> d;
    rep(j,2500){
      g.add_edge(2501*i+j,2501*i+min(j+c,(ll)2500),d);
    }
  }
  vector<ll> dist = g.dijkstra(min(s,(ll)2500));
  rep(i,1,n){
    ll ans = INF;
    rep(j,2501){
      chmin(ans,dist[2501*i+j]);
    }
    COUT(ans);
  }

	return;
}

int main()
{
	std::cin.tie(0);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}
