#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <queue>

using namespace std;

#define LL long long

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

LL mod(LL x, LL md) {
	return ((x % md) + md) % md;
}

class Mint {
public:
	static LL md;
	LL x;
	Mint(LL _x) {
		x = mod(_x, md);
	}
	Mint(const Mint &y) {
		x = mod(y.x, md);
	}
};

void MintMyExgcd(LL a, LL b, LL &x, LL &y) {
	// solve equation ax + by = 1 (mod m)
	LL md = Mint::md;
	if (b == 0) {
		y = 0;
		x = 1;
		return ;
	}
	MintMyExgcd(b, a % b, x, y);
	LL t = y;
	y = mod(x - (a / b) * y, md);
	x = t;
}

LL MintNY(LL x) {
	if (x == 0) {
		return 1;
	}
	LL md = Mint::md;
	LL a, b;
	MintMyExgcd(x, md, a, b);
	while (a < 0) {
		a += md;
	}
	return a;
}

/* LL gcd(LL a, LL b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
} */

Mint operator+(Mint a, Mint b) {
	return Mint(mod(a.x + b.x, Mint::md));
}
Mint operator-(Mint a, Mint b) {
	return Mint(mod(a.x - b.x, Mint::md));
}
Mint operator*(Mint a, Mint b) {
	return Mint(mod(a.x * b.x, Mint::md));
}
Mint operator/(Mint a, Mint b) {
	Mint c = Mint(MintNY(b.x));
	return Mint(mod(a.x * c.x, Mint::md));
}

Mint operator-(Mint a) {
	return Mint(-a.x);
}
bool operator==(Mint a, Mint b) {
	return a.x == b.x;
}
bool operator!=(Mint a, Mint b) {
	return a.x != b.x;
}
bool operator>(Mint a, Mint b) {
	return a.x > b.x;
}
bool operator<(Mint a, Mint b) {
	return a.x < b.x;
}
bool operator>=(Mint a, Mint b) {
	return a.x >= b.x;
}
bool operator<=(Mint a, Mint b) {
	return a.x <= b.x;
}

void operator+=(Mint &a, Mint b) {
	a = a + b;
}
void operator-=(Mint &a, Mint b) {
	a = a - b;
}
void operator*=(Mint &a, Mint b) {
	a = a * b;
}
void operator/=(Mint &a, Mint b) {
	a = a / b;
}

ostream& operator<<(ostream &out, Mint a) {
	out << a.x;
	return out;
}

istream& operator>>(istream &in, Mint &a) {
	in >> a.x;
	return in;
}

Mint factorial(LL n) {
	if (n == 0) {
		return Mint(1);
	}
	Mint res = 1;
	for (LL i = 1; i <= n; ++i) {
		res *= i;
	}
	return res;
}
Mint multiRange(LL s, LL t) {
	Mint res = 1;
	for (LL i = s; i <= t; ++i) {
		res *= i;
	}
	return res;
}

Mint getC(LL n, LL k) {
	if (n - k < k) {
		return getC(n, n - k);
	}
	return multiRange(n - k + 1, n) / factorial(k);
}

Mint getA(LL n, LL k) {
	return multiRange(n - k + 1, n);
}

Mint countNonNegativeDivision(LL n, LL k) {
	return getC(n + k - 1, k - 1);
}
Mint countPositiveDivision(LL n, LL k) {
	if (n < k) {
		return 0;
	}
	if (k <= 0) {
		return 0;
	}
	return getC(n - 1, k - 1);
}
Mint quickMod(Mint a, LL b) {
	Mint res = 1;
	while (b > 0) {
		if (b % 2) {
			res *= a;
		}
		a *= a;
		b /= 2;
	}
	return res;
}

LL Mint::md = 1000000007;

class Edge {
	public:
	int s, t, a, b;
	Edge(int _s, int _t, int _a, int _b): s(_s), t(_t), a(_a), b(_b) {}
};
class node {
	public:
	int v, s;
	LL dis;
	node(int _v, int _s, LL _dis): v(_v), s(_s), dis(_dis) {}
	node(const node &nd): v(nd.v), s(nd.s), dis(nd.dis) {}
};

bool operator<(const node &lhs, const node &rhs) {
	return lhs.dis > rhs.dis;
}

class Graph {
	public:
	Edge ***e;
	int n, m, S;
	int *c, *d;
	int maxTotal;
	LL **f;
	bool **vis;
	LL *ans;
	priority_queue<node> pq;
	int ansGot;
	bool **inq;
	int qSize;
	int *qv, *qs;
	int qh, qt;

	void addEdge(int u, int v, int a, int b) {
		u -= 1;
		v -= 1;
		e[u][v] = new Edge(u, v, a, b);
		e[v][u] = e[u][v];
	}

	Graph() {
		scanf("%d%d%d", &n, &m, &S);
		c = new int[n];
		d = new int[n];

		e = new Edge**[n];
		maxTotal = 50 * n;
		if (S > maxTotal) {
			S = maxTotal;
		}
		for (int i = 0; i < n; ++i) {
			e[i] = new Edge*[n];
			for (int j = 0; j < n; ++j) {
				e[i][j] = NULL;
			}
		}
		int u, v, a, b;
		for (int i = 0; i < m; ++i) {
			scanf("%d%d%d%d", &u, &v, &a, &b);
			addEdge(u, v, a, b);
		}
		for (int i = 0; i < n; ++i) {
			cin >> c[i] >> d[i];
		}

		f = new LL*[n];
		vis = new bool*[n];
		inq = new bool*[n];
		for (int i = 0; i < n; ++i) {
			f[i] = new LL[maxTotal + 1];
			vis[i] = new bool[maxTotal + 1];
			inq[i] = new bool[maxTotal + 1];
			for (int k = 0; k <= maxTotal; ++k) {
				f[i][k] = Mint::md;
				f[i][k] *= Mint::md;
				vis[i][k] = false;
				inq[i][k] = false;
			}
		}
		ans = new LL[n];
		for (int i = 0; i < n; ++i) {
			ans[i] = Mint::md;
			ans[i] *= Mint::md;
		}
		// ansGot = 0;
	}
	int getNext(int x) {
		return (x + 1) % qSize;
	}
	void update(int v, int s, LL dis) {
		// printf("update(%d, %d, %lld)\n", v, s, dis);
		if (!vis[v][s] || f[v][s] > dis) {
			vis[v][s] = true;
			f[v][s] = dis;

			if (!inq[v][s]) {
				qs[qt] = s;
				qv[qt] = v;
				qt = getNext(qt);
				inq[v][s] = true;
			}
		}
	}
	void SPFA() {
		f[0][S] = 0;
		vis[0][S] = true;
		inq[0][S] = true;

		qSize = n * (maxTotal + 1) + 10;
		qv = new int[qSize];
		qs = new int[qSize];

		qh = 0, qt = 1;
		qv[0] = 0;
		qs[0] = S;

		// ans[0] = 0;
		// ansGot += 1;
		ans[0] = 0;

		while (qh != qt) {
			int v = qv[qh], s = qs[qh];
			LL dis = f[v][s];
			// printf("work(%d, %d, %lld)\n", v, s, dis);
			// cout << "qh = " << qh << " qt = " << qt << endl;
			ans[v] = min(ans[v], dis);
			for (int i = 0; i < n; ++i) {
				if (e[v][i] && s >= e[v][i]->a) {
					update(i, s - e[v][i]->a, dis + (LL)(e[v][i]->b));
				}
			}
			LL transT = 0;
			for (int i = s; i <= maxTotal; i += c[v]) {
				transT += d[v];
				int ss = min(i + c[v], maxTotal);
				update(v, ss, dis + transT);
			}

			inq[v][s] = false;
			qh = getNext(qh);
		}
		// cout << "qSize = " << qSize << endl;

		for (int i = 1; i < n; ++i) {
			cout << ans[i] << endl;
		}
		// cout << f[2][0] << endl;

		// pq.push(node(0, S, 0));
		// while (ansGot < n) {
		// 	node nd = pq.top();
		// 	int v = nd.v;
		// 	int s = nd.s;
		// 	LL dis = nd.dis;
		// 	f[v][s] = dis;
		// 	if (ans[v] == -1) {
		// 		ans[v] = dis;
		// 		++ansGot;
		// 	}

		// 	for (int k = 0; k < n; ++k) {
		// 		if ()
		// 	}
		// }
	}
};

int main() {
	Graph g;
	g.SPFA();
	return 0;
}

Measured memory_bytes: 5904