/*
 ID: swagchicken1
 PROG:
 LANG: C++11
 */

#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;

#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)

//#define endl '\n';

#define mp make_pair
#define pb push_back
#define f first
#define s second

ll const inf = 1e18;
const int MOD = 1000000007;

long double PI = 4*atan(1);
long double eps = 1e-12;


ll dist[55][2555] = {};
ll n,m,si;
pair<ll,ll> ex[110] = {};
typedef pair <pair<ll ,ll> , ll>  node;

vector< vector <pair< ll, pair <ll ,ll > > > > adjlist(100);
//NEED: adjacency list, distance array
//NOTE: in adjacency list, weight comes FIRST

void dijkstra() {
    priority_queue<node, vector <node>, greater <node> > pq;
    ll start = min((ll) 2505, si);
    FOR(i,0,55) {
        FOR(j,0,2555) {
            dist[i][j] = inf;
        }
    }
    dist[1][start] = 0;
    pq.push(mp(mp(0,start), 1));
    while(!pq.empty()) {
        node curr = pq.top();
        pq.pop();
        ll d = curr.f.f;
        ll silver = curr.f.s;
        ll u = curr.s;
        //cout << u << " " << d << " " << silver << endl;
        if(d > dist[u][silver]) {
            continue;
        }
        
        if(silver + ex[u].f <= 2505) {
            if(dist[u][silver+ ex[u].f] > dist[u][silver] + ex[u].s) {
                dist[u][silver + ex[u].f] =dist[u][silver] + ex[u].s;
                pq.push(mp(mp(dist[u][silver + ex[u].f], silver + ex[u].f), u));
            }
        }

        FOR(j,0,adjlist[u].size()) {
            pair<ll, pair<ll, ll> > v = adjlist[u][j];
            if(silver >= v.s.f && dist[u][silver] + v.s.s < dist[v.f][silver - v.s.f]) {
                dist[v.f][silver-v.s.f] = dist[u][silver] + v.s.s;
                pq.push(mp(mp(dist[v.f][silver-v.s.f], silver-v.s.f), v.f));
            }
        }
    }
}


int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    //ofstream cout("output.txt");
    //ifstream cin("input.txt");
    cin >> n >> m >> si;
    
    
    FOR(i,0,m) {
        ll u,v,a,b; cin >> u >> v >> a >> b;
        adjlist[u].pb(mp(v,mp(a,b)));
        adjlist[v].pb(mp(u,mp(a,b)));
    }
    
    FOR(i,1,n+1) {
        ll c,d; cin >> c >> d;
        ex[i].f = c;
        ex[i].s = d;
    }
    
    dijkstra();
    
    FOR(i,2, n+1) {
        ll best = inf;
        FOR(j,0,2555) {
            best = min(best, dist[i][j]);
        }
        cout << best << endl;
    }

    
    
    
    //auto stop = chrono::high_resolution_clock::now();
    //auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    //cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}


Measured memory_bytes: 7440