#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
#define pp pair<ll,pair<int,int> >
const int M=52;
bool ed[M][M],vis[M][M*M];
int cst[M][M];ll c[M];
ll w[M][M],d[M];
ll dp[M][M*M],ans[M];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,a,b;
		cin>>u>>v>>a>>b;
		ed[u][v]=1;cst[u][v]=a;w[u][v]=b;
		swap(u,v);
		ed[u][v]=1;cst[u][v]=a;w[u][v]=b;	
	}
	for(int i=1;i<=n;i++)
		cin>>c[i]>>d[i];
	// cout<<c[2]<<" "<<d[2]<<endl;
	for(int i=1;i<=n;i++)
	{
		ans[i] = 1e18;
		for(int j=0;j<=2500;j++)
		{
			dp[i][j] = 1e18;
		}
	}
	if(s>2500)
		s=2500;
	dp[1][s] = 0;
	priority_queue<pp,vector<pp>,greater<pp> > pq;
	pq.push({dp[1][s],{1,s}});
	int ct = 0;
	while(!pq.empty())
	{
		auto P = pq.top();
		pq.pop();
		int x = P.ss.ff;
		ll y = P.ss.ss;
		if(vis[x][y])
			continue;
		vis[x][y]=1;
		ans[x] = min(ans[x],P.ff);
		ll p=c[x]+y;
		p=min(p,(ll)2500);
		if(dp[x][p]>dp[x][y]+d[x])
		{
			dp[x][p]=dp[x][y]+d[x];
			pq.push({dp[x][p],{x,p}});
		}
		for(int u=1;u<=n;u++)
		{
			if(ed[x][u]==0)
				continue;
			if(cst[x][u]<=y)
			{
				if(dp[u][y-cst[x][u]]>dp[x][y]+w[x][u])
				{
					dp[u][y-cst[x][u]]=dp[x][y]+w[x][u];
					pq.push({dp[u][y-cst[x][u]],{u,y-cst[x][u]}});
				}
			}
		}
	}
	for(int i=2;i<=n;i++)
		cout<<ans[i]<<"\n";
	return 0;
}