// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//


#define _USE_MATH_DEFINES
#include<math.h>

//#include<cmath>

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>



//#include "Ants.h"
using namespace std;
typedef long long ll;
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<n;i++)
#define show(s) cout<<s<<endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define LINF (1000000000000000000ll)
#define MOD (1e9+7)
typedef pair < ll, ll> P;
ll gcd(ll a, ll b) {//最大公約数を求める///最大公倍数a*b/gcd(a,b)
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcd(ll a, ll b) {//最小公倍数を求める　b=0のときaを返す
	if (b == 0) return a;
	return (a / gcd(a, b)) * b;
}
vector<int> divnum(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p;
}
int digiter(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p.size();
}
vector<int> convertstring(string s) {
	vector<int> d;
	ll n = s.size();
	rep(i, n) {
		d.push_back(s[i] - '0');
	}
	return d;
}
map< ll, int > prime_factor(ll n) {
	map< ll, int > ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}
vector<ll> divisor(ll n) {
	vector<ll>res;
	for (ll i = 1; i * i <= n; i++) {
		if (n % i != 0)continue;
		res.push_back(i);
		if (i * i != n)res.push_back(n / i);
	}
	return res;
}


ll myPow(ll x, ll n, ll m) {//x^n
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}
std::vector<int> Eratosthenes(const int N)//素数列挙
{
	std::vector<bool> is_prime(N + 1);
	for (int i = 0; i <= N; i++)
	{
		is_prime[i] = true;
	}
	std::vector<int> P;
	for (int i = 2; i <= N; i++)
	{
		if (is_prime[i])
		{
			for (int j = 2 * i; j <= N; j += i)
			{
				is_prime[j] = false;
			}
			P.emplace_back(i);
		}
	}
	return P;
}
const int mod = MOD;
struct mint {

	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x% mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
	mint operator+(const mint a) const { return mint(*this) += a; }
	mint operator-(const mint a) const { return mint(*this) -= a; }
	mint operator*(const mint a) const { return mint(*this) *= a; }
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const { return pow(mod - 2); }
	mint& operator/=(const mint a) { return *this *= a.inv(); }
	mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
struct combination {

	vector<mint> fact, ifact;
	combination(int n) :fact(n + 1), ifact(n + 1) {
		assert(n < mod);
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
		ifact[n] = fact[n].inv();
		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return fact[n] * ifact[k] * ifact[n - k];
	}
}comb(1000005);//comb貯め
mint f(int n, int k) {
	if (n < 0) return 0;
	// nPk = nCk * k!
	mint res = comb(n, k);
	res *= comb.fact[k];
	return res;
}

int Q;


struct SegmentTree {
private:
	int n;
	vector<int> node;

public:
	SegmentTree(vector<int> v) {
		int sz = v.size();
		n = 1; while (n < sz) n *= 2;
		node.resize(2 * n - 1, INF);
		for (int i = 0; i < sz; i++) node[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; i--) node[i] = min(node[2 * i + 1], node[2 * i + 2]);
	}

	void update(int x, int val) {
		x += (n - 1);
		node[x] = val;
		while (x > 0) {
			x = (x - 1) / 2;
			node[x] = min(node[2 * x + 1], node[2 * x + 2]);
		}
	}

	int getmin(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		if (r <= a || b <= l) return INF;
		if (a <= l && r <= b) return node[k];

		int vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
		int vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
};
struct Edge {
	int to, cost, time;
	Edge(int to,int cost,int time):to(to),cost(cost),time(time){}
};
int d[55][55],fare[55][55];int N, M, S, C[55], D[55]; 
int gpret[55][55];//gre[i][x]都市iで金貨x枚用意するための最善手時間
vector<Edge>G[55];
void warshall_floyd(int n) {
	rep(k, n) {
		rep(i, n) {
			rep(j, n) {
				if (d[i][j] > d[i][k] + d[k][j]) {
					d[i][j] = d[i][k] + d[k][j];
					fare[i][j] = fare[i][k] + fare[k][j];
				}
				//d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

int dist[55];  int mincost[55][55];
void dijkestra(int s) {
	fill(dist, dist + N, INF);
	rep(i, N)fill(mincost[i], mincost[i] + N, INF);
	priority_queue<P,vector<P>,greater<P>> que;
	dist[s] = 0;
	que.push(P(0, s));//cost,distination
	while (!que.empty()) {
		P p = que.top(); que.pop();
		ll v = p.second;
		if (dist[v] < p.second)continue;
		rep(x, 51) {
			mincost[v][x] = min(mincost[v][x], gpret[v][x]);
		}
		for (Edge t : G[v]) {
			ll need = t.cost;
			ll time = mincost[v][t.cost];
			time+=t.time;
			if (dist[t.to] > dist[v] + time) {
				dist[t.to] = dist[v] + time;
				que.push(P(dist[t.to], t.to));
			}
		}
	}
}


int main() {
	cin >> N >> M>>S;
	rep(i, N) { fill(d[i], d[i] + N, INF); fill(fare[i], fare[i] + N, INF); fill(gpret[i], gpret[i] + 51, INF); }

	rep(i, N) {d[i][i] = 0; fare[i][i] = 0;}
	rep(i, M) {
		int u, v, cost, time;
		cin >> u >> v >> cost >> time;
		u--; v--; d[u][v] = time; d[v][u] = time;fare[u][v] = cost; fare[v][u] = cost;
		G[u].push_back(Edge(v, cost, time));
		G[v].push_back(Edge(u, cost, time));
	}
	rep(i, N)cin >> C[i] >> D[i];
	warshall_floyd(N); 
	rep(u, N) {
		rep(v, N) {
			rep(x, 51) {
				int silver = x + fare[u][v] * 2;
				int cnt = (silver + C[v] - 1) / C[v];
				int cuexcht = cnt * D[v];
				gpret[u][x] = min(gpret[u][x], cuexcht + d[u][v] * 2);
			}
		}
	}
	
	dijkestra(0);
	rep(i, N) {
		rep(x, 5) {
			cout << i << " " << x << " " << gpret[i][x] << endl;
			cout << i << " " << x << " " << [i][x] << endl;
		}
	}
	rep(i, N-1) {
		cout << dist[i + 1] << endl;
	}

}
