#include<stdio.h>
#define l long
#define ll long long
#define INF 100000000000
#define new 1
#define used 0
#define min(x,y) x>y?y:x
#define val(a,c) a*2500+(c)

typedef struct dist {
    int to[50];
    l cost[50], past[50];
    int ume;
}DIST;

int N, M, S, U, V, A;
l B, C, D;
DIST dist[50];
ll city[50 * 2500];
int mark[50 * 2500];

void setting();

void input();

ll dikstr(int goal);

int main() {

    input();

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

        setting();

        printf("%lld\n", dikstr(i));

    };

};

void setting() {
    for (int i = 0; i < 50 * 2500; i++) {
        city[i] = INF;
        mark[i] = new;
    };
    city[S] = 0;
};

void input() {
    scanf("%d %d %d", &N, &M, &S);
    S=min(S,2499);
    for (int i = 0; i < 50; i++)dist[i].ume = -1;
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d %ld", &U, &V, &A, &B); U--; V--;
        dist[U].ume++; dist[V].ume++;
        dist[U].to[dist[U].ume] = V;
        dist[U].cost[dist[U].ume] = A;
        dist[U].past[dist[U].ume] = B;
        dist[V].to[dist[V].ume] = U;
        dist[V].cost[dist[V].ume] = A;
        dist[V].past[dist[V].ume] = B;
    };
    for (int i = 0; i < N; i++) {
        scanf("%ld %ld", &C, &D);
        dist[i].ume++;
        dist[i].to[dist[i].ume] = i;
        dist[i].cost[dist[i].ume] = C * -1;
        dist[i].past[dist[i].ume] = D;
        //printf("%d %d\n", i,dist[i].ume);
    };
};


ll dikstr(int goal) {
    ll mint;
    int present, money, mati;
    while (1) {
        mint = INF;
        for (int i = 0; i < N * 2500; i++) {
            if (mark[i] && mint > city[i]) {
                mint = city[i];
                present = i;
            };
        };
        mati = present / 2500;
        //printf("%d\n", mati);
        mark[present] = used;
        if (mati == goal)return city[present];
        money = present % 2500;
        for (int i = 0; i <= dist[mati].ume; i++) {
            if (money >= dist[mati].cost[i] && city[val(dist[mati].to[i] , min(money - dist[mati].cost[i], 2499))] > city[present] + dist[mati].past[i]) {
                city[val(dist[mati].to[i], min(money - dist[mati].cost[i], 2499))] = city[present] + dist[mati].past[i];
            };
        };
    };
};