#include <algorithm>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <numeric>
#include <limits>
#include <type_traits>


using namespace std;
#define SAY_YES cout << "YES" << endl;
#define SAY_Yes cout << "Yes" << endl;
#define SAY_NO cout << "NO" << endl;
#define SAY_No cout << "No" << endl;
#define IFYES(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "YES" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "NO" << endl;  \
    }
#define IFYes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "Yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "No" << endl;  \
    }
#define IFyes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "no" << endl;  \
    }
#define DEBUG_OUTPUT_ARRAY(XXX, ONE)                            \
    for (int i = 0; i < (ONE); i++)                             \
    {                                                           \
        cout << "DEBUG: i = " << i << " -> " << XXX[i] << endl; \
    }
#define DEBUG_OUTPUT_ARRAY2(XXX, ONE, TWO)                             \
    for (int i = 0; i < (ONE); i++)                                    \
    {                                                                  \
        cout << "<<< i = " << i << " >>>" << endl;                     \
        for (int j = 0; j < (TWO); j++)                                \
        {                                                              \
            cout << "DEBUG: j = " << j << " -> " << XXX[i][j] << endl; \
        }                                                              \
    }
#define DEBUG_OUTPUT_ARRAY2_BOX(XXX, ONE, TWO) \
    for (int i = 0; i < (ONE); i++)            \
    {                                          \
        cout << i << "  ";                     \
        for (int j = 0; j < (TWO); j++)        \
        {                                      \
            cout << XXX[i][j] << " ";          \
        }                                      \
        cout << endl;                          \
    }

typedef pair<long long int, long long int> pll;


const long long int mod = 1000000007;
const long long int INF = 1e18;
const long double PI=3.14159265358979323; 


long long int N,M,S,K,sum=0,res=0,A[105],B[105],C[100],D[100],P=2019;
long long int U[105],V[105];
long long int ten[200020]={1},appear[3000]={};
long long int silver[55][5050]={};
long long int needsilver[100]={};
vector<pll>Edge[55];
queue<long long int>task;

//INFを宣言すること。Edgeに辺の情報を入れよう。
class Graph{
//メンバ変数の説明
//Edge:一つ目の番号が辺が出る方向
//MaxV,MaxE:頂点数と辺の数
//Result系:各メソッドの答え
//InfinteUpdate:BellmanFordで各番号の頂点までの最短経路が更新されるか
//
public:
	vector<pair<long long int,long long int> > *Edge;
	vector<pair<pair<long long int,long long int>,long long int> >PrimEdge;
	long long int *InEdge;
	long long int MaxV,MaxE;
	long long int *BellmanFordResult,*DijkstraResult,**WarshallFloydResult;
	vector<long long int>TopologicalSortdVertex;
	bool *InfiniteUpdate;
	bool NegativeLoop=false;
	long long int PrimResult=0;
	bool NotConected=false;


	Graph(long long int InputV,long long int InputE){
		MaxV=InputV;
		MaxE=InputE;
		Edge=new vector<pair<long long int,long long int> >[InputV+1];

	}
    void updateE(long long int InputE){MaxE=InputE;return;}
	
	void BellmanFord(long long int Start) {
		BellmanFordResult=new long long int[MaxV];
		InfiniteUpdate=new bool[MaxV];
		for (int i = 0; i < MaxV; i++) { BellmanFordResult[i] = INF;InfiniteUpdate[i]=false; }
		BellmanFordResult[Start] = 0;
		long long int turn=0;
		while (true) {
			turn++;
			bool update = false;
			for (int i = 0; i < MaxV; i++) {
				for(int j=0;j<Edge[i].size();j++){
					pair<long long int,long long int> e = Edge[i][j];
					if(turn>=MaxV&&InfiniteUpdate[i])
					{
						InfiniteUpdate[e.first]=true;
					}
					if (BellmanFordResult[i] != INF && BellmanFordResult[e.first] > BellmanFordResult[i] + e.second) {
						BellmanFordResult[e.first] = BellmanFordResult[i] + e.second;
						update = true;
						if(turn>=MaxV){
							InfiniteUpdate[e.first]=true;
						}
					}
				}
			}
			if (!update) { 
				NegativeLoop=false;
				break; 
			}
			if(turn>=2*MaxV-1){
				NegativeLoop=true;
				break;
			}
		}
	}

	void Dijkstra(long long int Start) {
		DijkstraResult=new long long int[MaxV];
		priority_queue<pair<long long int,long long int>, vector<pair<long long int,long long int> >, greater<pair<long long int,long long int> > >que;
		fill(DijkstraResult, DijkstraResult + MaxV, INF);
		DijkstraResult[Start] = 0;
		que.push(pair<long long int,long long int>(0, Start));

		while (!que.empty()) {
			pair<long long int,long long int> p = que.top();
			que.pop();
			long long int v = p.second;
			if (DijkstraResult[v] < p.first)continue;
			for (int i = 0; i < Edge[v].size(); i++) {
				pair<long long int,long long int> e = Edge[v][i];
				if (DijkstraResult[e.first] > DijkstraResult[v] + e.second) {
					DijkstraResult[e.first] = DijkstraResult[v] + e.second;
					que.push(pair<long long int,long long int>(DijkstraResult[e.first], e.first));
				}
			}
		}
	}

	void WarshallFloyd() {
		WarshallFloydResult=new long long int*[MaxV];
		for(int i=0;i<MaxV;i++){
			WarshallFloydResult[i]=new long long int[MaxV];
		}
		for(int i=0;i<MaxV;i++){
			for(int j=0;j<Edge[i].size();j++){
				WarshallFloydResult[i][Edge[i][j].first]=Edge[i][j].second;
			}
		}

		for (int k = 0; k < MaxV; k++) {
			for (int i = 0; i < MaxV; i++) {
				for (int j = 0; j < MaxV; j++) {
					WarshallFloydResult[i][j] = min(WarshallFloydResult[i][j], WarshallFloydResult[i][k] + WarshallFloydResult[k][j]);
				}
			}
		}
	}
	void Prim(){
		NotConected=false;
		priority_queue<pair<long long int,pair<long long int,long long int> >,vector<pair<long long int,pair<long long int,long long int> > > ,greater<pair<long long int,pair<long long int,long long int> > > >PriorityEdge;
		bool *IncludedVertex=new bool[MaxV];
		fill(IncludedVertex,IncludedVertex+MaxV,false);
		PrimEdge.clear();
		for(int i=0;i<Edge[0].size();i++)
		{
			PriorityEdge.push({Edge[0][i].second,{0,Edge[0][i].first}});
		}
		IncludedVertex[0]=true;
		for(int i=0;i<MaxV-1;i++)
		{
			while(1)
			{
				if(PriorityEdge.empty())
				{
					NotConected=true;
					break;
				}
				pair<long long int,pair<long long int,long long int> > pe = PriorityEdge.top();
				PriorityEdge.pop();
				//cout<<pe.first<<" "<<pe.second.first<<" "<<pe.second.second<<endl;
				if(!IncludedVertex[pe.second.second])
				{
					IncludedVertex[pe.second.second]=true;
					PrimResult+=pe.first;
					PrimEdge.push_back({pe.second,pe.first});
					//cout<<"size"<<pe.second.second<<" "<<Edge[pe.second.second].size()<<endl;
					for(int j=0;j<Edge[pe.second.second].size();j++)
					{
						PriorityEdge.push({Edge[pe.second.second][j].second,{pe.second.second,Edge[pe.second.second][j].first}});
					}
					break;
				}
			}
		}
	}
    //おそらく未完成なトポロジカルソート
	void TopologicalSort(){
		bool notupdate=false;
		InEdge=new long long int[MaxV];
		TopologicalSortdVertex.clear();
		queue<long long int>task,firsttask;
		for(int i=0;i<MaxV;i++){
			InEdge[i]=0;
		}
		for(int i=0;i<MaxV;i++){
			for(int j=0;j<Edge[i].size();j++){
				InEdge[Edge[i][j].first]++;
			}
		}
		for(int i=0;i<MaxV;i++){
			if(InEdge[i]==0){
				firsttask.push(i);
			}

		}
		while(!firsttask.empty()){
			long long int i=firsttask.front();
			firsttask.pop();
			TopologicalSortdVertex.push_back(i);			
			InEdge[i]=-1;
			for(int j=0;j<Edge[i].size();j++){
				InEdge[Edge[i][j].first]--;
				if(InEdge[Edge[i][j].first]==0){
					task.push(Edge[i][j].first);
				}
			}
			

		}
		while(!task.empty()){
			long long int tmp=task.front();
			TopologicalSortdVertex.push_back(tmp);
			task.pop();
			if(InEdge[tmp]==0){
				InEdge[tmp]=-1;
				for(int j=0;j<Edge[tmp].size();j++){
					InEdge[Edge[tmp][j].first]--;
					if(InEdge[Edge[tmp][j].first]==0){
						task.push(Edge[tmp][j].first);
					}
				}
			}
			
		}
	}
};

int main()
{
    cout << fixed << setprecision(18);
    cin>>N>>M>>S;
    S=min(5000LL,S);
    Graph G(N*5001,0);
    long long int cou=0;
    for(long long int i = 0; i < M; i++){
        cin>>U[i]>>V[i]>>A[i]>>B[i];
        U[i]--;
        V[i]--;
        for(long long int j = 0; j <= 5000-A[i]; j++){
            cou++;
            G.Edge[U[i]+N*(j+A[i])].push_back({V[i]+N*j,B[i]});
            G.Edge[V[i]+N*(j+A[i])].push_back({U[i]+N*j,B[i]});
        }
        
    }
    for(long long int i = 0; i < N; i++){
        cin>>C[i]>>D[i];
        C[i]=min(5000LL,C[i]);
        for(long long int j = 0; j < 5000; j++){
            cou++;
            G.Edge[i+j*N].push_back({i+N*(min(j+C[i],5000LL)),D[i]});

        }
    }
    G.updateE(cou);
    G.Dijkstra(S*N+0);
    for(long long int i = 1; i < N; i++){
        long long int tmp=INF;
        for(long long int j = 0; j <= 5000; j++){
            //if(G.DijkstraResult[j*N+2]==10){cout<<j<<endl;}
            tmp = min(tmp,G.DijkstraResult[j*N+i]);
        }
        cout<<tmp<<endl;
    }
    

}    


Measured memory_bytes: 44436