// Slower C++ solution:
#include <bits/stdc++.h>

#define ps push_back

using namespace std;

const long long inf=9999999999999;

long long dp[52][2502];

struct nex{

    int x,cost,tim;

};

struct node{

    int x, s, t;

    bool operator<(const node& a)const{

        return t>a.t;

    }

};

priority_queue<node>que;

vector<nex>edg[52];

int c[52],d[52];

int book[52][2502];

int main()

{

    int u, v, a, b, s, n, m, i, j, k;

    cin>>n>>m>>s;

    s=min(2500, s);

    nex tmp;

    while(m--)

    {

        scanf("%d%d%d%d", &u,&v,&a,&b);

        tmp.x=v,tmp.cost=a,tmp.tim=b;

        edg[u].ps(tmp);

        tmp.x=u;

        edg[v].ps(tmp);

    }

    for(int i=1; i<=n; i++)scanf("%d%d", &c[i], &d[i]);

    for(i=0; i<=n; i++)

    {

        for(j=0; j<=2500; j++)

        {

            dp[i][j]=inf;

        }

    }

    dp[1][s]=0;

    node top;

    top.x=1;top.t=0;top.s=s;

    que.push(top);

//    top.x=2;top.t=1;top.s=s;

//    que.push(top);

//    printf("%d\n",que.top().x);

    while(!que.empty())

    {

        top=que.top();

        que.pop();

        int now=top.x, coin=top.s;

//        if(coin<10)printf("now%d coin%d %d\n", now, coin, dp[now][coin]);

        int nc=min(2500, coin+c[now]);

//        if(book[now][coin])continue;

//        book[now][coin]=1;

        if(dp[now][nc]>dp[now][coin]+d[now])

        {

            dp[now][nc]=dp[now][coin]+d[now];

//            if(book[now][nc])printf("%d %d %d\n", now, nc);

//            if(book[now][nc]==0){

            top.x=now,top.s=nc;

            top.t=dp[top.x][top.s];

            que.push(top);

//            }

        }

//        if(i<10)printf("nc%d %d\n", nc, dp[now][nc]);

        nex tmp;

        for(k=0; k<edg[now].size(); k++)

        {

            tmp=edg[now][k];

            j=coin;

//            if(i<10)printf("%d %d\n%d %d\n", now, tmp.x,j-tmp.cost, dp[tmp.x][j-tmp.cost]);





            if(j-tmp.cost>=0 && dp[now][j]+tmp.tim<dp[tmp.x][j-tmp.cost])

            {



                dp[tmp.x][j-tmp.cost]=dp[now][j]+tmp.tim;

//                if(book[tmp.x][j-tmp.cost]==0){

                    top.x=tmp.x;

                    top.s=j-tmp.cost;

                    top.t=dp[top.x][top.s];

                    que.push(top);

//                }

            }

        }



    }

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

    {

        long long mi=inf;

        for(j=0; j<=2500; j++)

        {

            mi=min(mi,dp[i][j]);

        }

        printf("%lld\n", mi);

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.0504980116799367x):
#include <bits/stdc++.h>

#define ps push_back

using namespace std;

const long long inf=9999999999999;

long long dp[52][2502];

struct nex{

    int x,cost,tim;

};

struct node{

    int x, s, t;

    bool operator<(const node& a)const{

        return t>a.t;

    }

};

priority_queue<node>que;

vector<nex>edg[52];

int c[52],d[52];

int book[52][2502];

int main()

{

    int u, v, a, b, s, n, m, i, j, k;

    cin>>n>>m>>s;

    s=min(2500, s);

    nex tmp;

    int ma=0;

    while(m--)

    {

        scanf("%d%d%d%d", &u,&v,&a,&b);

        ma=max(a,ma);

        tmp.x=v,tmp.cost=a,tmp.tim=b;

        edg[u].ps(tmp);

        tmp.x=u;

        edg[v].ps(tmp);

    }

    ma*=n;

    for(int i=1; i<=n; i++)scanf("%d%d", &c[i], &d[i]);

    for(i=0; i<=n; i++)

    {

        for(j=0; j<=2500; j++)

        {

            dp[i][j]=inf;

        }

    }

    dp[1][s]=0;

    node top;

    top.x=1;top.t=0;top.s=s;

    que.push(top);

//    top.x=2;top.t=1;top.s=s;

//    que.push(top);

//    printf("%d\n",que.top().x);

    while(!que.empty())

    {

        top=que.top();

        que.pop();

        int now=top.x, coin=top.s;

//        if(coin<10)printf("now%d coin%d %d\n", now, coin, dp[now][coin]);

        int nc=min(ma, coin+c[now]);

//        if(book[now][coin])continue;

//        book[now][coin]=1;

        if(dp[now][nc]>dp[now][coin]+d[now])

        {

            dp[now][nc]=dp[now][coin]+d[now];

//            if(book[now][nc])printf("%d %d %d\n", now, nc);

//            if(book[now][nc]==0){

            top.x=now,top.s=nc;

            top.t=dp[top.x][top.s];

            que.push(top);

//            }

        }

//        if(i<10)printf("nc%d %d\n", nc, dp[now][nc]);

        nex tmp;

        for(k=0; k<edg[now].size(); k++)

        {

            tmp=edg[now][k];

            j=coin;

//            if(i<10)printf("%d %d\n%d %d\n", now, tmp.x,j-tmp.cost, dp[tmp.x][j-tmp.cost]);





            if(j-tmp.cost>=0 && dp[now][j]+tmp.tim<dp[tmp.x][j-tmp.cost])

            {



                dp[tmp.x][j-tmp.cost]=dp[now][j]+tmp.tim;

//                if(book[tmp.x][j-tmp.cost]==0){

                    top.x=tmp.x;

                    top.s=j-tmp.cost;

                    top.t=dp[top.x][top.s];

                    que.push(top);

//                }

            }

        }



    }

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

    {

        long long mi=inf;

        for(j=0; j<=2500; j++)

        {

            mi=min(mi,dp[i][j]);

        }

        printf("%lld\n", mi);

    }

    return 0;

}