#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
//#define mod 998244353
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
using PP=pair<P,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline void out(T a){ cout << a << '\n'; }
void YN(bool ok){if(ok) cout << "Yes" << endl; else cout << "No" << endl;}
//void YN(bool ok){if(ok) cout << "YES" << endl; else cout << "NO" << endl;}


const ll INF=1e18;
const int mx=200005;

//dijkstra_class

struct edge{
    ll to,cost,pay;
};


ll dp[55][2505];


int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n,m,S;
    cin>>n>>m>>S;
    V<ll> u(m),v(m),a(m),b(m);
    V<ll> c(n),d(n);
    V<V<edge>> G(n);
    ll ma=0;
    rep(i,m){
        cin>>u[i]>>v[i]>>a[i]>>b[i];
        u[i]--;
        v[i]--;
        G[u[i]].pb((edge){v[i],b[i],a[i]});
        G[v[i]].pb((edge){u[i],b[i],a[i]});
        chmax(ma,a[i]);
    }
    
    rep(i,n){
        cin>>c[i]>>d[i];
    }
    for(ll i=0;i<n;i++){
        for(ll j=0;j<=ma*n;j++) dp[i][j]=INF;
    }
    priority_queue<PP,V<PP>,greater<PP>> que;
    if(S>ma*n) S=ma*n;
    /*for(ll i=0;i<=2500;i++){
        ll tmp=S+i*c[0];
        if(tmp>2500) tmp=2500;
        dp[0][tmp]=i*d[i];
        que.push(make_pair(P(dp[0][tmp],0),tmp));
        if(tmp==2500) break;
    }*/
    dp[0][S]=0;
    que.push(make_pair(P(0,0),S));
    while(!que.empty()){
        PP p=que.top();
        que.pop();
        ll v=p.ft.sc;
        ll mon=p.sc;
        if(dp[v][mon]<p.ft.ft) continue;
        for(int i=0;i<(int)G[v].size();i++){
            edge e=G[v][i];
            for(ll j=0;j<=ma*n;j++){
                ll cur=mon+j*c[v]-e.pay;
                if(cur>ma*n) cur=ma*n;
                if(cur>=0){
                    if(dp[e.to][cur]>dp[v][mon]+e.cost+j*d[v]){
                        dp[e.to][cur]=dp[v][mon]+e.cost+j*d[v];
                        que.push(make_pair(P(dp[e.to][cur],e.to),cur));
                    }
                }
                if(cur==ma*n) break;
            }
        }
    }
    for(int i=1;i<n;i++){
        ll ans=INF;
        for(int j=0;j<=ma*n;j++){
            chmin(ans,dp[i][j]);
        }
        out(ans);
    }
    /*rep(id,m){
        for(ll i=0;i<=2500;i++){//今銀貨をi枚保持
            for(ll j=0;(j-1)*c[u[id]]<=2500;j++){//銀貨をj枚追加
                if(i+j*c[u[id]]-a[id]>=0){
                    ds.add_edge(u[id]+i*n,v[id]+min((i+j*c[u[id]]-a[id]),2500LL)*n,b[id]+d[u[id]]*j);
                }
                if(i+j*c[u[id]]-a[id]>=2500) break;
            }
            for(ll j=0;(j-1)*c[v[id]]<=2500;j++){
                if(i+j*c[v[id]]-a[id]>=0){
                    ds.add_edge(v[id]+i*n,u[id]+min((i+j*c[v[id]]-a[id]),2500LL)*n,b[id]+d[v[id]]*j);
                }
                if(i+j*c[v[id]]-a[id]>=2500) break;
            }
        }
    }
    if(S>2500) S=2500;
    ds.exe(S*n);
    for(int i=1;i<n;i++){
        ll ans=INF;
        for(ll j=0;j<=2500;j++){
            chmin(ans,ds.dist_to(i+n*j));
        }
        out(ans);
    }*/
}

Measured memory_bytes: 53312