
#include<bits/stdc++.h>


using namespace std;

using ll   = long long;
using ii   = pair   < int , int >;
using i3   = pair   < int , ii  >;
using li   = pair   < ll  , int >;
using lii  = pair   < ll  , ii  >;
using pll  = pair   < ll  , ll  >;
using vi   = vector < int       >;
using vl   = vector < ll        >;
using vii  = vector < ii        >;
using vli  = vector < li        >;
using vpll = vector < pll       >;
using vi3  = vector < i3        >;
using vlii = vector < lii       >;


const int N = 100 + 5 , MAXS = 10000 + 5;
const ll INF = 1e17 + 7;
const double eps = 1e-9 , PI = acos(-1);


int n , m;

struct node {
    int v;
    int A;
    ll  B;

    node(){};
    node(int _v , int _A , ll _B) {
        v = _v;
        A = _A;
        B = _B;
    }
};

vector < node > adj[N];
int C[N];
int S;
ll D[N];

ll dis[N][MAXS];
int all = 0;

void djk() {

    for(int i = 0 ; i < N ; i ++) {
            for(int j = 0 ; j < MAXS ; j ++) {
                    dis[i][j] = INF;
            }
    }

    dis[1][S] = 0;
    priority_queue < lii , vlii , greater < lii > > pq;
    pq.push({0 , {S , 1} });

    while( !pq.empty() ) {
            ll  d = pq.top().first;
            int currS = pq.top().second.first;
            int u = pq.top().second.second;
            pq.pop();

            //cout << "u = " << u << " , d = " << d << " , currS = " << currS << endl;
            //system("pause");

            if(d != dis[u][currS]) continue;

            for(node nd : adj[u]) {
                    int v = nd.v;
                    ll  A = nd.A;
                    ll  B = nd.B;

                    for(int j = 0 ; j <= 10000 ; j ++) {
                            ll newS = currS + 1ll*j*C[u];
                            ll newD = d     + 1ll*j*D[u];

                            if(newS >= A) {
                                    ll costS = newS - A;
                                    if(newD + B < dis[v][costS]) {
                                            dis[v][costS] = newD + B;
                                            pq.push({newD + B , {costS , v} });
                                    }
                            }
                            if(newS > all) break;
                    }
            }
    }
}

void solve(int testCase){

    scanf("%d %d %d" , &n , &m , &S);

    S = min(S , 10000);

    for(int i = 0 ; i < m ; i ++) {
            int u , v;
            int A;
            ll  B;
            scanf("%d %d %d %lld" , &u , &v , &A , &B);
            all += A;

            adj[u].push_back(node(v , A , B));
            adj[v].push_back(node(u , A , B));
    }

    for(int i = 1 ; i <= n ; i ++) {
            scanf("%d %lld" , &C[i] , &D[i]);
            C[i] = min(C[i] , 5000);
    }

    djk();

    for(int i = 2 ; i <= n ; i ++) {
            ll ans = INF;
            for(int j = 0 ; j < MAXS ; j ++) {
                    ans = min(ans , dis[i][j]);
            }

            printf("%lld\n" , ans);
    }
}

main(){

    int t = 1;
    // scanf("%d" , &t);

    for(int testCase = 1 ; testCase <= t ; testCase ++){
            solve(testCase);
    }

    return 0;
}
