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

//TO_STRING
template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(char ch){
  string s;
  s += ch;
  return s;
}

string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + 
    to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + 
    to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

//DEBUG 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL //compile with -DLOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<pi> vpi;
typedef vector<char> vch;
typedef vector<string> vstr;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vvi> vvvi;
typedef vector<vvll> vvvll;
typedef vector<vch> vvch;
typedef vector<vstr> vvstr;

#define all(x) x.begin(), x.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second  
#define sz(x) ((ll)x.size())

const ll inf = 1e18;

struct Edge {
	int from, to, a;
	ll b;
};

typedef pair<ll, pi> tup;

struct cmp{ 				//cmp is a functor(struct that overloads () )
	bool operator()(tup a, tup b){
		return a > b;
	}
};

void solve() {
	ll n, m, s;
	cin >> n >> m >> s;

	ll max_silver = 2500;
	// vvvll dp(n + 1, vvll(n + 1, vll(max_silver + 1, inf)));

	s = min(s, max_silver);

	vector<Edge> edges;
	vvi adj(n + 1);
	vll c(n + 1), d(n + 1);

	for (int i = 0; i < m; i++) {
		int u, v, a, b;
		cin >> u >> v >> a >> b;
		adj[u].pb(sz(edges)); adj[v].pb(sz(edges));
		edges.pb({u, v, a, b});
	}

	for (int i = 1; i <= n; i++) {
		cin >> c[i] >> d[i];
	}


	vvll dp(n + 1, vll(max_silver + 1, inf));

	priority_queue<tup, vector<tup>, cmp> Q;
	Q.push({0, {s, 1}});

	vvb visited(n + 1, vb(max_silver + 1));

	while (!Q.empty()) {
		auto it = Q.top();
		Q.pop();
		// debug(it);
		ll dist = it.fi;
		int id = it.se.se, silver = it.se.fi;
		if (not visited[it.se.se][it.se.fi]) {
			visited[it.se.se][it.se.fi] = 1;
			dp[id][silver] = dist;
		} else {
			continue;
		}
		Q.push({dist + d[id], {min(max_silver, silver + c[id]), id}});

		for (int eid : adj[id]) {
			auto edge = edges[eid];
			int to = edge.from ^ edge.to ^ id;
			int req_silver = edge.a;
			ll time = edge.b;
			if (req_silver <= silver) {
				Q.push({dist + time, {silver - req_silver, to}});
			}
			ll next_silver = min(max_silver, silver - req_silver + c[id]);
			if (next_silver >= 0) {
				Q.push({dist + time + d[id], {next_silver, to}});
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		ll ans = inf;
		for (int silver = 0; silver <= max_silver; silver++) {
			ans = min(ans, dp[i][silver]);
		}
		cout << ans << "\n";
	}
}

int main() {
  ios::sync_with_stdio(false);  
  cin.tie(0);cout.tie(0); 
  
  int t = 1;
  for (int tc = 1; tc <= t; tc++) {
  	solve();
  }
}

Measured memory_bytes: 20760