#include<bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll          long long
#define pb          push_back
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define rs(v,n)     v.resize(n)
#define hell        1000000007
#define peak        9123372036854775807
#define pii         acos(-1)
#define clr(a,x)    memset(a,x,sizeof(a))
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class x,class y> x sum(x a,y b){return a+b;}
template<class x,class y> x mul(x a,y b){return a*b;}
template<class x,class y> x sub(x a,y b){return a-b;}
template<class x,class y> x divi(x a,y b){return a/b;}

template<class x,class y>
istream &operator>>(istream &in,pair<x,y> &p) 
{ 
    in>>p.F>>p.S;
    return in;
}
template<class x>
istream &operator>>(istream &in,vector<x> &v) 
{
    for(auto& i:v)
        in>>i;
    return in;
}
template<class x,class y>
ostream &operator<<(ostream &out,pair<x,y> &p) 
{ 
    out<<"("<<p.F<<","<<p.S<<") ";
    return out; 
}
template<class x>
ostream &operator<<(ostream &out,vector<x> &v) 
{ 
    out<<v.size()<<endl;
    for(auto i:v)
        out<<i<<" ";
    out<<endl;
    return out; 
}
#define N  1000005

vector<pair<ll,pair<ll,ll>>> v[55];

int main()
{
    ios;
    ll tt=1;
    // cin>>tt;
    while(tt--)
    {
        ll i,j,k,l,m,s,n;
        cin>>n>>m>>s;
        for(i=0;i<m;i++)
        {
            ll x,y;
            cin>>x>>y>>l>>k;
            v[x].pb({y,{l,k}});
            v[y].pb({x,{l,k}});
        }
        vector<pair<ll,ll>> cd(n+3);
        for(i=1;i<=n;i++)
        {
            cin>>cd[i].F>>cd[i].S;
        }
        priority_queue<pair<ll,pair<ll,ll>>> qu;
        vector<vector<ll>> dis(55,vector<ll>(2505,peak)),vis(55,vector<ll>(2505,0));
        // vis[1][min(2500ll,s)]=1;
        dis[1][min(2500ll,s)]=0;
        qu.push({-0,{1,min(2500ll,s)}});
        while(!qu.empty())
        {
            auto x=qu.top();
            if(vis[x.S.F][x.S.S]==1||dis[x.S.F][x.S.S]<-x.F) 
            {
                // cout<<-x.F<<" "<<x.S.F<<" "<<x.S.S<<endl;
                qu.pop();continue;
            }
            // cout<<-x.F<<" "<<x.S.F<<" "<<x.S.S<<endl;
            vis[x.S.F][x.S.S]=1;
            qu.pop();
            for(i=1;i<=10000;i++)
            {
                ll y=x.S.S+i*cd[x.S.F].F;
                if(y>=2500) y=2500;
                if(vis[x.S.F][y]==0&&dis[x.S.F][y]>dis[x.S.F][x.S.S]+i*cd[x.S.F].S)
                {
                    dis[x.S.F][y]=dis[x.S.F][x.S.S]+i*cd[x.S.F].S;
                    qu.push({-dis[x.S.F][y],{x.S.F,y}});
                }
                if(y>=2500) break;
            }
            for(auto i:v[x.S.F])
            {
                // cout<<i.S.F<<" "<<x.S.S<<" "<<i.F<<endl;
                if(i.S.F>x.S.S) continue;
                if(vis[i.F][x.S.S-i.S.F]==1) continue;
                if(dis[i.F][x.S.S-i.S.F]<=dis[x.S.F][x.S.S]+i.S.S) continue;
                dis[i.F][x.S.S-i.S.F]=dis[x.S.F][x.S.S]+i.S.S;
                qu.push({-dis[i.F][x.S.S-i.S.F],{i.F,x.S.S-i.S.F}});
            }
        }
        for(i=2;i<=n;i++)
        {
            ll ans=peak;
            for(j=0;j<=2500;j++)
                ans=min(ans,dis[i][j]);
            cout<<ans<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 103760