            #include <bits/stdc++.h>
            #include <ext/pb_ds/assoc_container.hpp>
            using namespace std;

            #define rep(i,a,b) for(ll i =a; i<b;++i)
            #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            #define endl "\n"
            #define pb push_back
            #define F first
            #define S second
            #define print(a)       for(auto x : a) cout << x << " "; cout << endl
            #define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
            #define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
            #define mk(x,y)  make_pair(x,y)
            typedef  long long  int ll;
            const ll N = ( 2e3 + 5 );
            const ll mod = 1e18+7;
            ll n,m,a[N],s,b[N],c[N],d[N],u[N],v[N],dp[55][55*55],ans[N];
            vector < pair<ll, pair <ll,ll >> > g[N];
    ll pow_mod_m(ll a , ll n)
    {
        if(!n)
            return 1;
        ll pt =  pow_mod_m(a,n/2);
        pt *= pt ;
        if(n&1)
            pt *= a ;
        return pt;
    }

    void dfs(ll u)
    {

    }

/// dp_i_j min time taken to reach j from i

    int main()
    {
         IOS;
         int ts =1;
         //cin>>ts;
         while(ts--)
         {
             cin >> n >> m >> s;
             s = min(s,2500ll);
             rep(i,1,m+1)
             {
                 cin >> u[i] >> v[i] >> a[i] >> b[i];
                 g[u[i]].pb(mk(v[i],mk(a[i],b[i])));
                 g[v[i]].pb(mk(u[i],mk(a[i],b[i])));
             }
             rep(i,1,n+1)
             {
                 cin >> c[i] >> d[i];
             }
             memset(dp , -1 , sizeof(dp));
             using T = pair<ll, pair <ll,ll > >;
             priority_queue < T , vector <T> , greater<T> > pq; /// {time , { node, silver}}
             pq.push(mk(0,mk(1,s)));
             while(pq.empty() == false)
             {
                 T w = pq.top();
                 pq.pop();
                 ll node = w.S.F;
                 ll silver = w.S.S;
                 if(dp[node][silver] != -1) continue;
                 dp[node][silver] = w.F;
                 if(silver < 2500)
                 {
                     pq.push( mk (w.F + d[node] , mk( node , silver + c[node]) ) );
                 }
                 for(auto v : g[node])
                 {
                     if(v.S.F <= silver and dp[v.F][silver - v.S.F] == -1)
                     {
                         pq.push( mk ( w.F + v.S.S , mk( v.F , silver - v.S.F )));
                     }
                 }
             }
             rep(i,2,n+1)
             {
                 ans[i] = mod;
                 rep(j,0,2501)
                 {
                     ans[i] = min(ans[i],dp[i][j]);
                 }
                 cout << ans[i] << endl;
             }
         }
    }
