/*
AuThOr GaRyMr
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl;
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
typedef pair<LL,pair<mp,int> > inf;
#define val FIR
#define from SEC.FIR.FIR
#define tim SEC.FIR.SEC
#define to SEC.SEC 
priority_queue<inf,vector<inf>,greater<inf> > q;
int n;
LL dp[51][2501];
vector<pair<int,mp> >  g[51];
int m,s;
int c[51],d[51];
int main(){
	fastio;
	cin>>n>>m>>s;
	s=min(s,2500);
	rb(i,1,m){
		int u,v,a,b;
		cin>>u>>v>>a>>b;
		g[u].PB(II(v,II(a,b)));
		g[v].PB(II(u,II(a,b)));
	}
	rb(i,1,n)
		cin>>c[i]>>d[i];
	
	rb(i,2,n)
	{
		LL res=1000000000000000000ll;
		rep(K,51)
			rep(L,2501)
				dp[K][L]=res;
		rep(j,2500)
			dp[i][j]=0,q.push(II(0,II(II(i,j),i)));
	while(!q.empty()){
		inf now=q.top();
		q.pop();
		int x,y,z;
		x=now.from;
		y=now.tim;
		z=now.to;
		if(now.val!=dp[x][y]) continue;
		if(dp[x][max(0,y-c[x])]>dp[x][y]+d[x]){
			dp[x][max(0,y-c[x])]=dp[x][y]+d[x];
			q.push(II(dp[x][max(0,y-c[x])],II(II(x,max(0,y-c[x])),z)));
		}
		for(auto it:g[x]){
				LL nval;int nx,ny,nz;
				nx=it.FIR;
				ny=y+it.SEC.FIR;
				ny=min(2500,ny);
				nz=z;
				nval=dp[x][y]+it.SEC.SEC;
				if(nval<dp[nx][ny]){
					dp[nx][ny]=nval;
					q.push(II(nval,II(II(nx,ny),nz)));
				}
		}
	}
	rep(j,s+1){
			res=min(res,dp[1][j]);
		}
		if(res<0){
			while(1);
		}
		cout<<res<<endl;
	}
	return 0;
}