// clang-format off
	#define BADSEED random_device{}()
	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	using uint = unsigned int;
	ostream &operator<<(ostream &os, int8_t c) { return os << short(c); }
	istream &operator>>(istream &is, int8_t &c) { short x; is >> x; c = x; return is; }
	#define TM_(...) template <class __VA_ARGS__>
	namespace narut {
	TM_(T) using TupSz = tuple_size<decay_t<T>>;
	TM_(T) constexpr auto spc(T const &t, int) -> decltype((cout << t), 'a') { return ' '; }
	constexpr auto spc(string const &s, int) { return '\n'; }
	TM_(T) constexpr auto spc(T const &t, char) { return '\n'; }
	struct IO {
		TM_(T) static auto out_(ostream &os, T const &t, int) -> decltype(void(os << t)) { os << t; }
		TM_(T, class OS) static auto out_(OS &os, T const &t, int) -> decltype(void(begin(t))) {
			auto it = begin(t), e = end(t);
			if (it != e) out_(os, *it++, 0);
			for (; it != e; out_(os, *it++, 0)) os << spc(*it, 0);
		}
		TM_(T, size_t... Is) static void out_tup(ostream &os, T const &t, index_sequence<Is...>) { (void)initializer_list<int>{0, ((Is == 0) ? 0 : ((os << ' '), 0), (os << get<Is>(t)), 0)...}; }
		TM_(T) static decltype(void(TupSz<T>{})) out_(ostream &os, T const &t, char) { out_tup(os, t, make_index_sequence<TupSz<T>::value>{}); }
		TM_(Sep, class F, class... Ts) static ostream &print(ostream &os, Sep sep, F const &f, Ts const &... ts) { return void(initializer_list<int>{(out_(os, f, 0), 0), (out_(os << sep, ts, 0), 0)...}), os; }
		TM_(T) static auto in_(istream &is, T &t, int) -> decltype(void(is >> t)) { is >> t; }
		TM_(T, class IS) static auto in_(IS &is, T &t, int) -> decltype(void(begin(t))) { for (auto &x : t) in_(is, x, 0); }
		TM_(T, size_t... Is) static void in_tup(istream &is, T &t, index_sequence<Is...>) { (void)initializer_list<int>{0, (in_(is, get<Is>(t), 0), 0)...}; }
		TM_(T) static decltype(void(TupSz<T>{})) in_(istream &is, T &t, char) { in_tup(is, t, make_index_sequence<TupSz<T>::value>{}); }
	};
	} // namespace narut
	#define Cout(...) narut::IO::print(cout, ' ', __VA_ARGS__) << '\n'
	#ifdef NARUT_LOCAL
	#define Debug(...) narut::IO::print(cerr << "\033[0;31m", ", ", __VA_ARGS__) << "\033[0m\n"
	#else
	#define Debug(...) 0
	#endif
	[[maybe_unused]] struct Cin {
		template <class T> Cin const &operator>>(T &t) const { return narut::IO::in_(cin, t, 0), *this; }
		template <class T> operator T() const { T t; return *this >> t, t;  }
	} Cin;
	TM_(T) auto operator%(T &t, size_t n) -> decltype(t.resize(n), t)& { return t.resize(n), t; }
	#define FOR(i, j, n) for (int i = int(j); i < int(n); ++i)
	#define ROF(i, j, n) for (int i = int(n) - 1; i >= int(j); --i)

// clang-format on

template <class T, class = void> struct Greater {
	constexpr bool operator()(const T &lhs, const T &rhs) const { return rhs < lhs; }
};
template <class T>
struct Greater<T, decltype((void)(declval<T &>() > declval<T &>()))> : greater<T> {};
template <class T> using MaxPQ = priority_queue<T>;
template <class T> using MinPQ = priority_queue<T, vector<T>, Greater<T>>;

const int MXC = 5000;

int n, m, s;
vector<vector<ll>> dist;
vector<vector<array<int, 3>>> G;
vector<pair<int, int>> CD;

auto Read() {
	cin >> n >> m >> s;
	dist.assign(n + 1, vector<ll>(MXC, 0x3f3f3f3f3f3f3f3f));

	G % (n + 1);
	CD % (n + 1);

	FOR(mi, 0, m) {
		int u, v, a, b;
		cin >> u >> v >> a >> b;
		G[u].push_back({v, a, b});
		G[v].push_back({u, a, b});
	}
	FOR(ni, 1, n + 1) { cin >> CD[ni].first >> CD[ni].second; }
}

auto Main() {
	Read();

	s = min(MXC - 1, s);
	dist[1][s] = 0;

	using E = tuple<ll, int, int>;
	MinPQ<E> pq;
	pq.emplace(0, 1, s);

	while (pq.size()) {
		auto [d, u, c] = pq.top();
		pq.pop();

		if (dist[u][c] != d) continue;

		for (const auto &[v, a, b] : G[u]) {
			if (c < a) continue;
			auto alt = d + b;
			if (alt < dist[v][c - a]) {
				dist[v][c - a] = alt;
				pq.emplace(alt, v, c - a);
			}
		}

		auto [ex_c, ex_d] = CD[u];
		auto alt = d + ex_d;
		auto c2 = min(MXC - 1, c + ex_c);
		if (alt < dist[u][c2]) {
			dist[u][c2] = alt;
			pq.emplace(alt, u, c2);
		}
	}

	FOR(u, 2, n + 1) { Cout(*min_element(begin(dist[u]), end(dist[u]))); }
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(10);
#ifdef NARUT_LOCAL
	assert(freopen("io/test.in", "r", stdin));
	cin.exceptions(cin.badbit | cin.failbit);
	cerr << fixed << setprecision(10);
#endif

	Main();
}


Measured memory_bytes: 9344