#include<stdio.h>
#define l long
#define ll long long
#define INF 50000000000
#define new 1
#define used 0
#define min(x,y) x>y?y:x

typedef struct dist {
    int ume;
    int citynum[2600];
    ll cost[2600];
}DIST;

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

int setting();

int input();

ll dikstr(int goal);

int main() {

    input();

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

        setting();

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

    };

};

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

int input() {
    scanf_s("%d%d%d", &N, &M, &S);
    for (int i = 0; i < 50 * 2500; i++)dist[i].ume = 0;
    for (int i = 0; i < M; i++){
        scanf_s("%d%d%d%ld", &U, &V, &A, &B); U--; V--;
        for (int j = A; j < 2500; j++) {
            dist[U * 2500 + j].citynum[++dist[U * 2500 + j].ume ] = V * 2500 + j - A;
            dist[U * 2500 + j].cost[dist[U * 2500 + j].ume] = B;
            dist[V * 2500 + j].citynum[++dist[V * 2500 + j].ume ] = U * 2500 + j - A;
            dist[V * 2500 + j].cost[dist[V * 2500 + j].ume] = B;
        };
    };
    for (int i = 0; i < N; i++) {
        scanf_s("%ld%ld", &C, &D);
        for (int j = 0; j < 2498; j++) {
            dist[i * 2500 + j].citynum[++dist[i * 2500 + j].ume]=i * 2500 + min(j + C, 2499);
            dist[i * 2500 + j].cost[dist[i * 2500 + j].ume] = D;
        };
    };
};

ll dikstr(int goal) {
    ll mint;
    int present;
    while (1) {
        mint = INF;
        for (int i = 0; i < N * 2500; i++) {
            if (mark[i] && mint > city[i]) {
                mint = city[i];
                present = i;
                mark[i] = used;
            };
        };
        if (present >= goal * 2500 && present < (goal + 1) * 2500)
            return city[present];
        for (int i = 0; i <= dist[present].ume; i++) {
            if (city[dist[present].citynum[i] ]> city[present] + dist[present].citynum[i]) {
                city[dist[present].citynum[i]] = city[present] + dist[present].citynum[i];
            };
        };
    };
};
