/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

// the states are (node, coins at this node)
// used a Dijkstra variation
// the no. of "coins at a node" are bounded by the total no. of coins required to traverse all edges

#include<bits/stdc++.h>
using namespace std;

#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)(x.size()))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     makep           make_pair
#define     maket           make_tuple
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)+(x)-1)/(x))
#define     gcd(a,b)        (__gcd((a),(b)))
#define     lcm(a,b)        (((a)*(b))/gcd((a),(b)))
#define     dbug(x)         cout<<#x<<": "<<(x)<<"\n"
#define     flush           fflush(stdout)
#define     show(x)         for(auto zz:x)cout<<zz<<" ";cout<<"\n";
#define     show2(x)        for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const ld pi=acos(-1);
const ll inf=1e18,M=1e9+7;
const int N=52;

vi adj[N];
pii mat[N][N];

void solve()
{
    int n,m,s;
    cin>>n>>m>>s;

    int tot=0;
    int u,v,a,b;
    for(int i=0;i<m;++i)
    {
        cin>>u>>v>>a>>b;
        mat[u][v]={a,b};
        mat[v][u]={a,b};

        adj[u].pb(v);
        adj[v].pb(u);

        tot+=a;
    }

    vector<pii> val(n+1);
    int c,d;
    for(int i=1;i<=n;++i)
    {
        cin>>c>>d;
        val[i]={c,d};
    }

    priority_queue<tuple<int,int,int>> pq;           // (-time, coins, node)

    vector<vi> tim(n+1,vi(tot+1,inf));               // (node, coins at this node)

    tim[1][0]=0;
    pq.push(maket(0,min(s,tot+1),1));

    int cur,coins,x;
    int req;
    while(!pq.empty())
    {
        tie(cur,coins,x)=pq.top();
        pq.pop();

        cur*=-1;

        for(auto c:adj[x])
        {
            req=mat[x][c].F;

            if(req>coins)
                continue;

            int& tmp=tim[c][coins-req];
            if(coins-req<=tot && tmp>cur+mat[x][c].S)
            {
                tmp=cur+mat[x][c].S;
                pq.push(maket(-tmp,coins-req,c));
            }
        }

        int& tmp=tim[x][coins+val[x].F];
        if(coins+val[x].F<=tot && tmp>cur+val[x].S)
        {
            tmp=cur+val[x].S;
            pq.push(maket(-tmp,coins+val[x].F,x));
        }
    }

    for(int i=2;i<=n;++i)
        cout<<*min_element(all(tim[i]))<<"\n";
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 7432