//69行目から編集
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define repn for(int i = 0;i < n;i++)
#define ain(a) for(auto& i : a)cin >> i;
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size())
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define cont continue

//Simple Array Input
#define SAI int n;cin >> n;vi a(n);ain(a)
//Simple Graph Input
#define SGI(m) for(int i=0;i<m;i++){int a,b;cin >> a >> b;g[--a].pb(--b);g[b].pb(a);}
//Simple Tree Input
#define STI SGI(n-1)

typedef long long ll;
typedef long long integer;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > vvi;
typedef vector<vector<ll> > vvl;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

template<class T> bool chmin(T& a,T b){if(a > b){a = b;return true;}else return false;}
template<class T> bool chmax(T& a,T b){if(a < b){a = b;return true;}else return false;}
template<class T> void print(std::vector<T> a){
    for(int i=0;i<a.size();i++)cout << a[i] << (i < a.size()-1 ? ' ' : '\n');
}
///////////////////////////////////////////////////////////
/*
    Dijkstra's algorithm
    qt : https://kopricky.github.io/code/Graph_SP_MST/dijkstra.html
    last checked : 2020.4.22
*/
template<typename T> class Dijkstra {
public:
    struct edge{
        int to; T cost;
    };
    int V;
    vector<vector<edge> > G;
    vector<T> d;
    using pti = pair<T,int>;
    vector<int> prev;
    Dijkstra(int node_size) : V(node_size), G(V), d(V, numeric_limits<T>::max()),prev(node_size,-1){}
    void add_edge(int u,int v,T cost){
        G[u].push_back((edge){v,cost});
    }
    void solve(int s){
        priority_queue<pti,vector<pti>,greater<pti> > que;
        d[s] = 0;
        que.push(pti(0,s));
        while(!que.empty()){
            pti p = que.top();
            que.pop();
            int v = p.second;
            if(d[v] < p.first) continue;
            for(auto& w : G[v]){
                if(d[w.to] > d[v] + w.cost){
                    d[w.to] = d[v] + w.cost;
                    prev[w.to] = v;
                    que.push(pti(d[w.to],w.to));
                }
            }
        }
    }
    vector<int> get_path(int s,int t){
        vector<int> res;
        while(t != s){
            res.push_back(t);
            t = prev[t];
        }
        res.push_back(s);
        reverse(res.begin(),res.end());
        return res;
    }
};

/*
    add_edge : 辺を追加
    solve : dijkstraを実行する 
*/
const int maxn = 51;
const int maxm = 110;

int n,m;
ll s;

int u[maxm],v[maxm];
ll a[maxm],b[maxm],c[maxm],d[maxm];

int id;
map<pair<int,ll>,int> get_id;

Dijkstra<ll> G(51*5011);

int main(int argc, char const *argv[])
{
	//cin.tie(0);ios::sync_with_stdio(false);

	cin >> n >> m >> s;
    if(s >= 5010)s = 5010;
	//各辺の情報を受け取る
	rep(i,m)cin >> u[i] >> v[i] >> a[i] >> b[i];
	rep(i,m)u[i]--,v[i]--;
	//頂点ごとの換金レートの情報を受け取る
	rep(i,n)cin >> c[i] >> d[i];

	//受け取った情報からグラフを構築する
	{
		//番号、銀貨の枚数をペアにした頂点と頂点番号との対応を作る
		{
			rep(i,n)rep(j,5011){
				get_id[make_pair(i,j)] = id++;
			}
		}
		//状態から状態への辺を張る
		{
			//往復の辺について、各頂点の可能な全ての金額状態から行先の対応する金額状態への辺として全て張る
			{
				rep(i,m){
					int f = u[i];
					int t = v[i];
					ll cost = a[i];
					ll time = b[i];
					for(ll from = cost;from <= 5010;from++){
						ll to = from - cost;

						int id_from = get_id[make_pair(f,from)];
						int id_to = get_id[make_pair(t,to)];

						G.add_edge(id_from,id_to,time);
					}
					for(ll from = cost;from <= 5010;from++){
						ll to = from - cost;

						int id_from = get_id[make_pair(t,from)];
						int id_to = get_id[make_pair(f,to)];

						G.add_edge(id_from,id_to,time);
					}
				}
			}
			//自分の都市について、金貨を銀貨に変換する辺を張る
			{
				rep(i,n){
					ll cost = c[i];
					ll time = d[i];

					for(ll now = 0;now + cost <= 5010;now++){
						ll after = now + cost;

						int id_now = get_id[make_pair(i,now)];
						int id_aft = get_id[make_pair(i,after)];

						G.add_edge(id_now,id_aft,time);
					}
				}	
			}
		}
	}


	//ダイクストラを実行する
	int start_id = get_id[make_pair(0,s)];
	G.solve(start_id);

	//拡張点について、最短時間を出力する
	for(int i = 1;i < n;i++){
		long long ans = LONG_MAX;
		for(int j = 0;j <= 5010;j++){
			int id = get_id[make_pair(i,j)];
			chmin(ans,G.d[id]);
		}
		cout << ans << '\n';
	}
	return 0;
}

Measured memory_bytes: 61176