#include<bits/stdc++.h>
 
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define INF 1e18

 
typedef long long ll;
ll mod = 998244353;

 long long fast_exp(long long a, long long b)
{
    if(b <= 0)
       return 1;
    else
    {
       long long res = 1;
       res = fast_exp(a,b/2);
       res = (res*res)%mod;
       if(b%2 == 1)
          res = (res*a)%mod;
       return res;
 
    }
}
typedef long double ld;
const long long N = 2e5+5;
struct ed{
    ll u,v,a,b;
};
vector <ed> edge[51];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n, m, s, u, v, a, b;
    cin >> n >> m >> s;
    for(ll i = 0; i<m ; i++)
    {
        cin >> u >> v >> a >> b;
        ed e1;
        e1.u = u, e1.v = v, e1.a = a, e1.b = b;
        edge[u].pb(e1);
        e1.u = v;
        e1.v = u;
        edge[v].pb(e1);
    }
    ll c[n+1], d[n+1];
    for(ll i = 1; i<=n ; i++)
        cin >> c[i] >> d[i]; 
    ll dp[n+1][2501];
    ll vis[n+1][2501] = {};
    for(ll i = 0; i<=n ; i++)
        for(ll j = 0; j<2501 ; j++)
            dp[i][j] = INF;
    
    s = min(s,2500LL);
    dp[1][s] = 0;
    set< pair<ll,pair<ll,ll>> > q;
    q.insert({0,{1,s}});
    while(!q.empty())
    {
        pair<ll,pair<ll,ll>> cur = *q.begin();
        q.erase(cur);
        ll i = cur.ss.ff, j = cur.ss.ss;
        for(auto e: edge[i])
        {
            if(j >= e.a && dp[e.v][j-e.a] > dp[i][j] + e.b)
            {
                if(q.find({dp[e.v][j-e.a],{e.v,j-e.a}}) != q.end())
                    q.erase({dp[e.v][j-e.a],{e.v,j-e.a}});
                    dp[e.v][j-e.a] = dp[i][j] + e.b;
                    q.insert({dp[e.v][j-e.a],{e.v,j-e.a}});
            }
        }

        ll ni = i, nj = min(j + c[i],2500LL);
        if(dp[ni][nj] > dp[i][j] + d[i])
        {
            if(q.find({dp[ni][nj],{ni,nj}}) != q.end())
                q.erase({dp[ni][nj],{ni,nj}});
            dp[ni][nj] = dp[i][j] + d[i];
            q.insert({dp[ni][nj],{ni,nj}});
        }    
    }

    ll ans[n+1];
    for(ll i = 2; i<=n ; i++)
    {
        ans[i] = INF;
        for(ll j = 0; j<=2500; j++)
            ans[i] = min(ans[i],dp[i][j]);
    } 

    for(ll i = 2; i<=n ; i++)
        cout<< ans[i] << '\n';





  
    return 0;
 
 
}