#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<unordered_map>
#include<set>
#include<cmath>
#include<random>

//#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define ALL(v) (v).begin() , (v).end()
#define fast ios::sync_with_stdio(false); cin.tie(NULL);
const double eps = 1e-6;

/////////////////////////////////////////////

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

////////////////////////////////

#define int long long
const int N = 102;
int c[N];
int d[N];

vector<vector<int>> v[52];

int dist[52][2600];

void solve(){

	int n , m , s;
	cin>>n>>m>>s;

	s = min(s , 2500LL);
	for(int i = 1 ; i <=m ; ++i){

		int x, y , p , q;
		cin>>x>>y>>p>>q;
		v[x].pb({y , p , q});
		v[y].pb({x , p , q});
	}

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

		cin>>c[i]>>d[i];
	}
	memset(dist , -1 , sizeof dist);
	priority_queue<pair<int,pair<int,int>> , vector<pair<int,pair<int,int>>> , greater<pair<int,pair<int,int>>>> pq;

	pq.push({0 , {1 , s}});

	while(!pq.empty()){

		auto x = pq.top();
		pq.pop();
		int node = x.ss.ff;
		int coin = x.ss.ss;
		int cost = x.ff;
		coin = min(coin , 2500LL);
		if(dist[node][coin]!=-1)
			continue;

		dist[node][coin] = cost;
		// Trying to start with higher number of coins .
		if(coin < 2500) pq.push({cost + d[node] , {node , c[node] + coin}});
		for(auto it : v[node]){

			if(it[1] <= coin && dist[it[0]][coin - it[1]]==-1){

				pq.push({cost + it[2] , {it[0] ,coin - it[1]}}); // Just go the min with the condtions .
			}
		}
	}

	for(int i = 2 ; i <= n ; ++i){

		int cost = 1e18;

		for(int j = 0 ; j <= 2500 ; ++j)
			if(dist[i][j]!=-1)
				cost = min(cost , dist[i][j]);
		cout<<cost<<endl;
	}
}

signed main(){

    fast;
    //freopen("output.txt" , "w" , stdout);
    int t = 1;
   // cin>>t;
    for(int i = 1 ; i <= t; ++i){

    	solve();
    }
}


Measured memory_bytes: 10464