// Slower C++ solution:
 #include <bits/stdc++.h>

 



//tabaicho  see https://boostjp.github.io/tips/multiprec-int.html   

// #include <boost/multiprecision/cpp_int.hpp>

// using namespace boost::multiprecision;



// cpp_int

// int128_t

// int256_t

// int512_t

// int1024_t



// uint128_t

// uint256_t

// uint512_t

// uint1024_t







 #define int long long

 #define inf  1000000007

// #define inf  998244353



 #define pa pair<int,int>

 #define ll long long

 #define PI 3.14159265358979323846

 #define  mp make_pair

 #define  pb push_back

 #define EPS (1e-8)

 

      using namespace std;

                                          

 int dx[8]={0,1,0,-1,1,1,-1,-1};

 int dy[8]={1,0,-1,0,-1,1,1,-1};

                                            

class pa3{

	public:

	int x;

	int y,z;

	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}

	bool operator < (const pa3 &p) const{

		if(x!=p.x) return x<p.x;

		if(y!=p.y) return y<p.y;

		 return z<p.z;

		//return x != p.x ? x<p.x: y<p.y;

	}

	bool operator > (const pa3 &p) const{

		if(x!=p.x) return x>p.x;

		if(y!=p.y) return y>p.y;

		 return z>p.z;

		//return x != p.x ? x<p.x: y<p.y;

	}

	bool operator == (const pa3 &p) const{

		return x==p.x && y==p.y && z==p.z;

	}

		bool operator != (const pa3 &p) const{

			return !( x==p.x && y==p.y && z==p.z);

	}



};



class pa4{

	public:

	int x;

	int y,z,w;

	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}

	bool operator < (const pa4 &p) const{

		if(x!=p.x) return x<p.x;

		if(y!=p.y) return y<p.y;

		if(z!=p.z)return z<p.z;

		return w<p.w;

		//return x != p.x ? x<p.x: y<p.y;

	}

	bool operator > (const pa4 &p) const{

		if(x!=p.x) return x>p.x;

		if(y!=p.y) return y>p.y;

		if(z!=p.z)return z>p.z;

		return w>p.w;

		//return x != p.x ? x<p.x: y<p.y;

	}

	bool operator == (const pa4 &p) const{

		return x==p.x && y==p.y && z==p.z &&w==p.w;

	}

		



};

class pa2{

	public:

	int x,y;

	pa2(int x=0,int y=0):x(x),y(y) {}

	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}

	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}

	bool operator < (const pa2 &p) const{

		return y != p.y ? y<p.y: x<p.x;

	}

	bool operator > (const pa2 &p) const{

		return x != p.x ? x<p.x: y<p.y;

	}

	bool operator == (const pa2 &p) const{

		return abs(x-p.x)==0 && abs(y-p.y)==0;

	}

	bool operator != (const pa2 &p) const{

		return !(abs(x-p.x)==0 && abs(y-p.y)==0);

	}

		



};







string itos( int i ) {

	ostringstream s ;

	s << i ;

	return s.str() ;

}

 

int Gcd(int v,int b){

	if(v==0) return b;

	if(b==0) return v;

	if(v>b) return Gcd(b,v);

	if(v==b) return b;

	if(b%v==0) return v;

	return Gcd(v,b%v);

}





 int mod;

int extgcd(int a, int b, int &x, int &y) {

    if (b == 0) {

        x = 1;

        y = 0;

        return a;

    }

    int d = extgcd(b, a%b, y, x);

    y -= a/b * x;

    return d;

}

pa operator+(const pa & l,const pa & r) {   

    return {l.first+r.first,l.second+r.second};                                    

}    

pa operator-(const pa & l,const pa & r) {   

    return {l.first-r.first,l.second-r.second};                                    

}  



ostream& operator<<(ostream& os, const vector<int>& VEC){

	for(auto v:VEC)os<<v<<" ";

    return os;

}



ostream& operator<<(ostream& os, const pa& PAI){

	os<<PAI.first<<" : "<<PAI.second;

    return os;

}



ostream& operator<<(ostream& os, const pa3& PAI){

	os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z;

    return os;

}



ostream& operator<<(ostream& os, const pa4& PAI){

	os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z<<" : "<<PAI.y;

    return os;

}









int beki(int wa,int rr,int warukazu){

	if(rr==0) return 1%warukazu;

	if(rr==1) return wa%warukazu;

	wa%=warukazu;

	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;

	ll zx=beki(wa,rr/2,warukazu);

	return (zx*zx)%warukazu;

}



              

int pr[1100000];

int inv[1100000];







int comb(int nn,int rr){

	if(rr<0 || rr>nn || nn<0) return 0;

	int r=pr[nn]*inv[rr];

	r%=mod;

	r*=inv[nn-rr];

	r%=mod;

	return r;

}



void gya(int ert){

	pr[0]=1;

	for(int i=1;i<=ert;i++){

		pr[i]=((ll)pr[i-1]*i)%mod;

	}

		inv[ert]=beki(pr[ert],mod-2,mod);

	for(int i=ert-1;i>=0;i--){

		inv[i]=(ll)inv[i+1]*(i+1)%mod;

	}

}





                





                

              //   cin.tie(0);

    		//	ios::sync_with_stdio(false);

    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            

                 //sort(ve.begin(),ve.end(),greater<int>());

 //   mt19937(clock_per_sec);

  //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;



struct fibonacci_heap{

	

	using Key=int;

	using Val=pa;

	

	int sz=0;

	

	struct fh_node{

		int deg;

		bool cut;

		

		fh_node* prv;

		fh_node* nxt;

		fh_node* par;

		fh_node* chi;

		

		Key key;

		Val val;

		

		fh_node(){

			deg=0;

			cut=0;

			prv=nullptr;

			nxt=nullptr;

			par=nullptr;

			chi=nullptr;	

		}

		

		fh_node(Key k,Val v){

			deg=0;

			cut=0;

			prv=nullptr;

			nxt=nullptr;

			par=nullptr;

			chi=nullptr;	

			key=k;

			val=v;

		}

		

	};

	

	private:

	public:

	

	fh_node* deglist[100];

	

	fh_node* ROOT;





	

	

	fh_node* mp_node[52][3010]={};

	fh_node* get_node(Val val){

		return mp_node[val.first][val.second];

	}

	void set_node(Val val ,fh_node* node){

		mp_node[val.first][val.second]=node;

	}

	

	void unset_node(Val val){

		mp_node[val.first][val.second]=nullptr;

	}

	

	

	fibonacci_heap(){

		ROOT = new fh_node;

		for(int i=0;i<100;i++)deglist[i]=nullptr;

	}

	

	// kirihanasu

	// node is not root of tree

	void make_new_tree(fh_node* node){

		fh_node* tmp=node->par;

		tmp->deg--;

		if(node->nxt==node){

			tmp->chi=nullptr;

		}

		else{

			if(tmp->chi==node)tmp->chi=node->nxt;

			

			node->nxt->prv=node->prv;

			node->prv->nxt=node->nxt;

		}

		

		node->par=ROOT;

		ROOT->chi->nxt->prv=node;

		node->nxt=ROOT->chi->nxt;

		ROOT->chi->nxt=node;

		node->prv=ROOT->chi;

		if(node->key<ROOT->chi->key)ROOT->chi=node;

		

	}

	

	void decrease_key(fh_node* node,Key key){

		node->key=key;

		if(node->par==ROOT){

			if(node->key<=ROOT->chi->key)ROOT->chi=node;

			return;

		}

		if(node->par->key<=key) return;

		

		fh_node* tmp=node->par;

		

		node->cut=0;

		

		make_new_tree(node);

		

		while(1){

			if(tmp->par==ROOT)break;

			if(tmp->cut==0){

				tmp->cut=1;

				break;

			}

			

			tmp->cut=0;

			node=tmp->par;

			make_new_tree(tmp);

			tmp=node;

		}

		

	}

	

	

	fh_node* merge(fh_node* v1,fh_node* v2){

		assert(v1->deg==v2->deg);

		if(v1->key>v2->key)swap(v1,v2);

		v1->deg++;

		if(v1->deg==1){

			v1->chi=v2;

			v2->nxt=v2;

			v2->prv=v2;

			v2->par=v1;

		}

		else{

			v1->chi->nxt->prv=v2;

			v2->nxt=v1->chi->nxt;

			v2->prv=v1->chi;

			v2->par=v1;

			v1->chi->nxt=v2;

			

		}

		return v1;

	}

	

	void merge_trees(){

		if(ROOT->chi==nullptr)return;

		

		fh_node* new_node=nullptr;

		fh_node* old_node=ROOT->chi;

		fh_node* tmp;

		

		old_node->prv->nxt=nullptr;

		

		while(1){

			tmp=old_node;

			old_node=old_node->nxt;

			

			if(new_node==nullptr){

				new_node=tmp;

				tmp->prv=nullptr;

				tmp->nxt=nullptr;

				deglist[tmp->deg]=tmp;

			}

			else{

				

				while(1){

					if(deglist[tmp->deg]==nullptr){

						deglist[tmp->deg]=tmp;

						tmp->nxt=new_node;

						tmp->prv=nullptr;

						if(new_node!=nullptr)new_node->prv=tmp;

						new_node=tmp;

						break;

					}

					

					fh_node* tmp2=deglist[tmp->deg];

					deglist[tmp->deg]=nullptr;

					

					if(tmp2->prv==nullptr && tmp2->nxt==nullptr){

						new_node=nullptr;

					}

					else if(tmp2->prv==nullptr){

						new_node=tmp2->nxt;

						tmp2->nxt->prv=nullptr;

					}

					else if(tmp2->nxt==nullptr){

						tmp2->prv->nxt=nullptr;

					}

					else{

						tmp2->prv->nxt=tmp2->nxt;

						tmp2->nxt->prv=tmp2->prv;

					}

					

					tmp=merge(tmp,tmp2);

				}

			}

			

			

			if(old_node==nullptr) break;

		}

		

		ROOT->chi=new_node;

		tmp=new_node;

		

		while(1){

			if(ROOT->chi->key>tmp->key){

				ROOT->chi=tmp;

			}

			deglist[tmp->deg]=nullptr;

			if(tmp->nxt==nullptr)break;

			tmp=tmp->nxt;

		}

		tmp->nxt=new_node;

		new_node->prv=tmp;

	}

	

	void push(Key key, Val val){

		

		

		

		fh_node* node=get_node(val);

		

		if(node!=nullptr){

			assert(node->key>=key);

			if(node->key>key)decrease_key(node,key);

		}

		else if(sz==0){

			sz++;

			node=new fh_node(key,val);

			ROOT->chi=node;

			node->prv=node;

			node->nxt=node;

			node->par=ROOT;

			set_node(val,node);

		}

		else{

			sz++;

			node=new fh_node(key,val);

			node->par=ROOT;

			node->prv=ROOT->chi;

			node->nxt=ROOT->chi->nxt;

			node->nxt->prv=node;

			ROOT->chi->nxt=node;

			if(ROOT->chi->key>key)ROOT->chi=node;

			set_node(val,node);

		}

		

	

	}

	

	pair<Key,Val> top(){

		assert(sz);

		return mp(ROOT->chi->key,ROOT->chi->val);

	}

	

	pair<Key,Val> pop(){

	

		assert(sz);	

		fh_node* erase_node=ROOT->chi;

		auto ans=mp(ROOT->chi->key,ROOT->chi->val);

		if(ROOT->chi->deg){

			fh_node* tmp =ROOT->chi->chi;

			while(tmp->par!=ROOT){

				tmp->par=ROOT;

				tmp=tmp->prv;

			}

			if(erase_node->prv==erase_node){

				ROOT->chi=tmp;

			}

			else{

				tmp->prv->nxt=erase_node->nxt;

				erase_node->nxt->prv=tmp->prv;

				erase_node->prv->nxt=tmp;

				tmp->prv=erase_node->prv;

				ROOT->chi=ROOT->chi->nxt;

			}

		}

		else{

			if(erase_node->prv==erase_node){

				ROOT->chi=nullptr;

		//		cout<<sz<<endl;

				assert(sz==1);

			}

			else{

				ROOT->chi=erase_node->prv;

				erase_node->prv->nxt=erase_node->nxt;

				erase_node->nxt->prv=erase_node->prv;

			}

		}

		sz--;

		

		merge_trees();

		

		unset_node(ans.second);

		delete erase_node;

	//	cout<<erase_node->key<<endl;

	//	cout<<ROOT->chi->key<<endl;

		

		

		//if(sz==14)exit(0);

		return ans;

	}

	

	void show(){

		show(ROOT);

	}

	

	void show(fh_node* node){

		if(node!=ROOT){

			if(node==ROOT->chi)cout<<"!!"<<endl;

			cout<<node->par->val<<" | "<<node->val<<" | "<<node->deg<<endl;

		}

		node=node->chi;

		if(node!=nullptr){

			if(node->par==ROOT || true){

			while(1){

				show(node);

				node=node->nxt;

				if(node->nxt==node->par->chi)break;

			}

			}

			else{

				int g=node->par->deg;

				for(int i=0;i<g;i++){

				show(node);

				node=node->nxt;

				//if(node->nxt==node->par->chi)break;

				}

			}

		}

	}

	

	int size(){

		return sz;

	}

};







vector<pa3> G[60];



int vis[60][3010];



void solve(){

	fibonacci_heap fh;

	

	int n,m,s;

	cin>>n>>m>>s;

	s=min(s,3000ll);

	for(int i=0;i<m;i++){

		int y,yy,yyy,yyyy;

		cin>>y>>yy>>yyy>>yyyy;

		G[y].pb({yy,yyy,yyyy});

		G[yy].pb({y,yyy,yyyy});

		

	}

	int c[60],d[60];

	for(int i=1;i<=n;i++)cin>>c[i]>>d[i];

	for(int i=0;i<60;i++)for(int j=0;j<3010;j++)vis[i][j]=inf*100000000ll;

	

	vis[1][s]=0;

	fh.push(0,mp(1,s));

	int ans[60]={};

	while(fh.size()){

		auto z=fh.pop();

		int pos=z.second.first;

		int gin=z.second.second;

		

		if(ans[pos]==0){

			ans[pos]=z.first;

		}

		

		if(gin<3000){

			if(vis[pos][min(3000ll,gin+c[pos])]>z.first+d[pos]){

				vis[pos][min(3000ll,gin+c[pos])]=z.first+d[pos];

				fh.push(z.first+d[pos],mp(pos,min(3000ll,gin+c[pos])));

				

			}

		}

		for(auto v:G[pos])if(gin-v.y>=0)if(vis[v.x][gin-v.y]>z.first+v.z){

			vis[v.x][gin-v.y]=z.first+v.z;

			fh.push(z.first+v.z,mp(v.x,gin-v.y));

		}

	}

	for(int i=2;i<=n;i++)cout<<ans[i]<<endl;

	

}

 

signed main(){

	

	cin.tie(0);

	ios::sync_with_stdio(false);

int n=1;

	//cin>>n;

 

	

	for(int i=0;i<n;i++)solve();

	

	return 0;

 }

// Faster C++ solution for the same problem (measured speedup: 1.5165990317826588x):
 #include <bits/stdc++.h>

 



//tabaicho  see https://boostjp.github.io/tips/multiprec-int.html   

// #include <boost/multiprecision/cpp_int.hpp>

// using namespace boost::multiprecision;



// cpp_int

// int128_t

// int256_t

// int512_t

// int1024_t



// uint128_t

// uint256_t

// uint512_t

// uint1024_t







 #define int long long

 #define inf  1000000007

// #define inf  998244353



 #define pa pair<int,int>

 #define ll long long

 #define PI 3.14159265358979323846

 #define  mp make_pair

 #define  pb push_back

 #define EPS (1e-8)

 

      using namespace std;

                                          

 int dx[8]={0,1,0,-1,1,1,-1,-1};

 int dy[8]={1,0,-1,0,-1,1,1,-1};

                                            

class pa3{

	public:

	int x;

	int y,z;

	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}

	bool operator < (const pa3 &p) const{

		if(x!=p.x) return x<p.x;

		if(y!=p.y) return y<p.y;

		 return z<p.z;

		//return x != p.x ? x<p.x: y<p.y;

	}

	bool operator > (const pa3 &p) const{

		if(x!=p.x) return x>p.x;

		if(y!=p.y) return y>p.y;

		 return z>p.z;

		//return x != p.x ? x<p.x: y<p.y;

	}

	bool operator == (const pa3 &p) const{

		return x==p.x && y==p.y && z==p.z;

	}

		bool operator != (const pa3 &p) const{

			return !( x==p.x && y==p.y && z==p.z);

	}



};



class pa4{

	public:

	int x;

	int y,z,w;

	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}

	bool operator < (const pa4 &p) const{

		if(x!=p.x) return x<p.x;

		if(y!=p.y) return y<p.y;

		if(z!=p.z)return z<p.z;

		return w<p.w;

		//return x != p.x ? x<p.x: y<p.y;

	}

	bool operator > (const pa4 &p) const{

		if(x!=p.x) return x>p.x;

		if(y!=p.y) return y>p.y;

		if(z!=p.z)return z>p.z;

		return w>p.w;

		//return x != p.x ? x<p.x: y<p.y;

	}

	bool operator == (const pa4 &p) const{

		return x==p.x && y==p.y && z==p.z &&w==p.w;

	}

		



};

class pa2{

	public:

	int x,y;

	pa2(int x=0,int y=0):x(x),y(y) {}

	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}

	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}

	bool operator < (const pa2 &p) const{

		return y != p.y ? y<p.y: x<p.x;

	}

	bool operator > (const pa2 &p) const{

		return x != p.x ? x<p.x: y<p.y;

	}

	bool operator == (const pa2 &p) const{

		return abs(x-p.x)==0 && abs(y-p.y)==0;

	}

	bool operator != (const pa2 &p) const{

		return !(abs(x-p.x)==0 && abs(y-p.y)==0);

	}

		



};







string itos( int i ) {

	ostringstream s ;

	s << i ;

	return s.str() ;

}

 

int Gcd(int v,int b){

	if(v==0) return b;

	if(b==0) return v;

	if(v>b) return Gcd(b,v);

	if(v==b) return b;

	if(b%v==0) return v;

	return Gcd(v,b%v);

}





 int mod;

int extgcd(int a, int b, int &x, int &y) {

    if (b == 0) {

        x = 1;

        y = 0;

        return a;

    }

    int d = extgcd(b, a%b, y, x);

    y -= a/b * x;

    return d;

}

pa operator+(const pa & l,const pa & r) {   

    return {l.first+r.first,l.second+r.second};                                    

}    

pa operator-(const pa & l,const pa & r) {   

    return {l.first-r.first,l.second-r.second};                                    

}  



ostream& operator<<(ostream& os, const vector<int>& VEC){

	for(auto v:VEC)os<<v<<" ";

    return os;

}



ostream& operator<<(ostream& os, const pa& PAI){

	os<<PAI.first<<" : "<<PAI.second;

    return os;

}



ostream& operator<<(ostream& os, const pa3& PAI){

	os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z;

    return os;

}



ostream& operator<<(ostream& os, const pa4& PAI){

	os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z<<" : "<<PAI.y;

    return os;

}









int beki(int wa,int rr,int warukazu){

	if(rr==0) return 1%warukazu;

	if(rr==1) return wa%warukazu;

	wa%=warukazu;

	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;

	ll zx=beki(wa,rr/2,warukazu);

	return (zx*zx)%warukazu;

}



              

int pr[1100000];

int inv[1100000];







int comb(int nn,int rr){

	if(rr<0 || rr>nn || nn<0) return 0;

	int r=pr[nn]*inv[rr];

	r%=mod;

	r*=inv[nn-rr];

	r%=mod;

	return r;

}



void gya(int ert){

	pr[0]=1;

	for(int i=1;i<=ert;i++){

		pr[i]=((ll)pr[i-1]*i)%mod;

	}

		inv[ert]=beki(pr[ert],mod-2,mod);

	for(int i=ert-1;i>=0;i--){

		inv[i]=(ll)inv[i+1]*(i+1)%mod;

	}

}





                





                

              //   cin.tie(0);

    		//	ios::sync_with_stdio(false);

    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            

                 //sort(ve.begin(),ve.end(),greater<int>());

 //   mt19937(clock_per_sec);

  //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;



struct fibonacci_heap{

	

	using Key=int;

	using Val=pa;

	

	int sz=0;

	

	struct fh_node{

		int deg;

		bool cut;

		

		fh_node* prv;

		fh_node* nxt;

		fh_node* par;

		fh_node* chi;

		

		Key key;

		Val val;

		

		fh_node(){

			deg=0;

			cut=0;

			prv=nullptr;

			nxt=nullptr;

			par=nullptr;

			chi=nullptr;	

		}

		

		fh_node(Key k,Val v){

			deg=0;

			cut=0;

			prv=nullptr;

			nxt=nullptr;

			par=nullptr;

			chi=nullptr;	

			key=k;

			val=v;

		}

		

	};

	

	private:

	public:

	

	fh_node* deglist[100];

	

	fh_node* ROOT;





	

	

	fh_node* mp_node[52][3010]={};

	fh_node* get_node(Val val){

		return mp_node[val.first][val.second];

	}

	void set_node(Val val ,fh_node* node){

		mp_node[val.first][val.second]=node;

	}

	

	void unset_node(Val val){

		mp_node[val.first][val.second]=nullptr;

	}

	

	

	fibonacci_heap(){

		ROOT = new fh_node;

		for(int i=0;i<100;i++)deglist[i]=nullptr;

	}

	

	// kirihanasu

	// node is not root of tree

	void make_new_tree(fh_node* node){

		fh_node* tmp=node->par;

		tmp->deg--;

		if(node->nxt==node){

			tmp->chi=nullptr;

		}

		else{

			if(tmp->chi==node)tmp->chi=node->nxt;

			

			node->nxt->prv=node->prv;

			node->prv->nxt=node->nxt;

		}

		

		node->par=ROOT;

		ROOT->chi->nxt->prv=node;

		node->nxt=ROOT->chi->nxt;

		ROOT->chi->nxt=node;

		node->prv=ROOT->chi;

		if(node->key<ROOT->chi->key)ROOT->chi=node;

		

	}

	

	void decrease_key(fh_node* node,Key key){

		node->key=key;

		if(node->par==ROOT){

			if(node->key<=ROOT->chi->key)ROOT->chi=node;

			return;

		}

		if(node->par->key<=key) return;

		

		fh_node* tmp=node->par;

		

		node->cut=0;

		

		make_new_tree(node);

		

		while(1){

			if(tmp->par==ROOT)break;

			if(tmp->cut==0){

				tmp->cut=1;

				break;

			}

			

			tmp->cut=0;

			node=tmp->par;

			make_new_tree(tmp);

			tmp=node;

		}

		

	}

	

	

	fh_node* merge(fh_node* v1,fh_node* v2){

		assert(v1->deg==v2->deg);

		if(v1->key>v2->key)swap(v1,v2);

		v1->deg++;

		if(v1->deg==1){

			v1->chi=v2;

			v2->nxt=v2;

			v2->prv=v2;

			v2->par=v1;

		}

		else{

			v1->chi->nxt->prv=v2;

			v2->nxt=v1->chi->nxt;

			v2->prv=v1->chi;

			v2->par=v1;

			v1->chi->nxt=v2;

			

		}

		return v1;

	}

	

	void merge_trees(){

		if(ROOT->chi==nullptr)return;

		

		fh_node* new_node=nullptr;

		fh_node* old_node=ROOT->chi;

		fh_node* tmp;

		

		old_node->prv->nxt=nullptr;

		

		while(1){

			tmp=old_node;

			old_node=old_node->nxt;

			

			if(new_node==nullptr){

				new_node=tmp;

				tmp->prv=nullptr;

				tmp->nxt=nullptr;

				deglist[tmp->deg]=tmp;

			}

			else{

				

				while(1){

					if(deglist[tmp->deg]==nullptr){

						deglist[tmp->deg]=tmp;

						tmp->nxt=new_node;

						tmp->prv=nullptr;

						if(new_node!=nullptr)new_node->prv=tmp;

						new_node=tmp;

						break;

					}

					

					fh_node* tmp2=deglist[tmp->deg];

					deglist[tmp->deg]=nullptr;

					

					if(tmp2->prv==nullptr && tmp2->nxt==nullptr){

						new_node=nullptr;

					}

					else if(tmp2->prv==nullptr){

						new_node=tmp2->nxt;

						tmp2->nxt->prv=nullptr;

					}

					else if(tmp2->nxt==nullptr){

						tmp2->prv->nxt=nullptr;

					}

					else{

						tmp2->prv->nxt=tmp2->nxt;

						tmp2->nxt->prv=tmp2->prv;

					}

					

					tmp=merge(tmp,tmp2);

				}

			}

			

			

			if(old_node==nullptr) break;

		}

		

		ROOT->chi=new_node;

		tmp=new_node;

		

		while(1){

			if(ROOT->chi->key>tmp->key){

				ROOT->chi=tmp;

			}

			deglist[tmp->deg]=nullptr;

			if(tmp->nxt==nullptr)break;

			tmp=tmp->nxt;

		}

		tmp->nxt=new_node;

		new_node->prv=tmp;

	}

	

	void push(Key key, Val val){

		

		

		

		fh_node* node=get_node(val);

		

		if(node!=nullptr){

			assert(node->key>=key);

			if(node->key>key)decrease_key(node,key);

		}

		else if(sz==0){

			sz++;

			node=new fh_node(key,val);

			ROOT->chi=node;

			node->prv=node;

			node->nxt=node;

			node->par=ROOT;

			set_node(val,node);

		}

		else{

			sz++;

			node=new fh_node(key,val);

			node->par=ROOT;

			node->prv=ROOT->chi;

			node->nxt=ROOT->chi->nxt;

			node->nxt->prv=node;

			ROOT->chi->nxt=node;

			if(ROOT->chi->key>key)ROOT->chi=node;

			set_node(val,node);

		}

		

	

	}

	

	pair<Key,Val> top(){

		assert(sz);

		return mp(ROOT->chi->key,ROOT->chi->val);

	}

	

	pair<Key,Val> pop(){

	

		assert(sz);	

		fh_node* erase_node=ROOT->chi;

		auto ans=mp(ROOT->chi->key,ROOT->chi->val);

		if(ROOT->chi->deg){

			fh_node* tmp =ROOT->chi->chi;

			while(tmp->par!=ROOT){

				tmp->par=ROOT;

				tmp=tmp->prv;

			}

			if(erase_node->prv==erase_node){

				ROOT->chi=tmp;

			}

			else{

				tmp->prv->nxt=erase_node->nxt;

				erase_node->nxt->prv=tmp->prv;

				erase_node->prv->nxt=tmp;

				tmp->prv=erase_node->prv;

				ROOT->chi=ROOT->chi->nxt;

			}

		}

		else{

			if(erase_node->prv==erase_node){

				ROOT->chi=nullptr;

		//		cout<<sz<<endl;

				assert(sz==1);

			}

			else{

				ROOT->chi=erase_node->prv;

				erase_node->prv->nxt=erase_node->nxt;

				erase_node->nxt->prv=erase_node->prv;

			}

		}

		sz--;

		

		merge_trees();

		

		unset_node(ans.second);

		delete erase_node;

	//	cout<<erase_node->key<<endl;

	//	cout<<ROOT->chi->key<<endl;

		

		

		//if(sz==14)exit(0);

		return ans;

	}

	

	void show(){

		show(ROOT);

	}

	

	void show(fh_node* node){

		if(node!=ROOT){

			if(node==ROOT->chi)cout<<"!!"<<endl;

			cout<<node->par->val<<" | "<<node->val<<" | "<<node->deg<<endl;

		}

		node=node->chi;

		if(node!=nullptr){

			if(node->par==ROOT || true){

			while(1){

				show(node);

				node=node->nxt;

				if(node->nxt==node->par->chi)break;

			}

			}

			else{

				int g=node->par->deg;

				for(int i=0;i<g;i++){

				show(node);

				node=node->nxt;

				//if(node->nxt==node->par->chi)break;

				}

			}

		}

	}

	

	int size(){

		return sz;

	}

};







vector<pa3> G[60];



int vis[60][3010];



void solve(){

	fibonacci_heap fh;

	

	int n,m,s;

	cin>>n>>m>>s;

	s=min(s,n*50);

	for(int i=0;i<m;i++){

		int y,yy,yyy,yyyy;

		cin>>y>>yy>>yyy>>yyyy;

		G[y].pb({yy,yyy,yyyy});

		G[yy].pb({y,yyy,yyyy});

		

	}

	int c[60],d[60];

	for(int i=1;i<=n;i++)cin>>c[i]>>d[i];

	for(int i=0;i<60;i++)for(int j=0;j<3010;j++)vis[i][j]=inf*100000000ll;

	

	vis[1][s]=0;

	fh.push(0,mp(1,s));

	int ans[60]={};

	while(fh.size()){

		auto z=fh.pop();

		int pos=z.second.first;

		int gin=z.second.second;

		

		if(ans[pos]==0){

			ans[pos]=z.first;

		}

		

		if(gin<n*50){

			if(vis[pos][min(n*50,gin+c[pos])]>z.first+d[pos]){

				vis[pos][min(n*50,gin+c[pos])]=z.first+d[pos];

				fh.push(z.first+d[pos],mp(pos,min(n*50,gin+c[pos])));

				

			}

		}

		for(auto v:G[pos])if(gin-v.y>=0)if(vis[v.x][gin-v.y]>z.first+v.z){

			vis[v.x][gin-v.y]=z.first+v.z;

			fh.push(z.first+v.z,mp(v.x,gin-v.y));

		}

	}

	for(int i=2;i<=n;i++)cout<<ans[i]<<endl;

	

}

 

signed main(){

	

	cin.tie(0);

	ios::sync_with_stdio(false);

int n=1;

	//cin>>n;

 

	

	for(int i=0;i<n;i++)solve();

	

	return 0;

 }