#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef long long   ll;
#define pb                push_back
#define mp                make_pair
#define all(a)            (a).begin(), (a).end()
#define clr(a,h)          memset(a, (h), sizeof(a))
#define mem(a,h)          memset(a, (h), sizeof(a))
#define fi first
#define se second
#define por(a,b) (((a%MOD) * (b%MOD))%MOD)
#define forg(i, b, e, c)    for (ll i = (ll)b; i < (ll)e; i+=c)
#define forr(i, b, e)    for (ll i = b; i < e; i++)
 
 
using namespace std;
//using namespace __gnu_pbds;
typedef double lldb;
typedef pair<int, int>  ii;
typedef pair<ll, ii>  iii;
typedef vector<ll>     vi;
typedef vector<vi>     vvi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll INF = 1e9;
const double PI = acos(-1);
#define tam 300000
#define offset 
const ll MOD= 1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {

template < class c > struct rge { c b, e; };
template < class c > rge<c> range(c i, c j) { return rge<c>{i, j}; }
template < class c > auto dud(c* x) -> decltype(cerr << *x, 0);
template < class c > char dud(...);

struct debug {
    ~debug() { cerr << endl; }
    
    //     Part 1
    
    template < class c > typename \
    enable_if<sizeof dud<c>(0) != 1, debug&>::type operator<<(c i) {
        cerr << boolalpha << i;
        return * this;
    }
    
    //     Part 2
    
    template < class c > typename \
    enable_if<sizeof dud<c>(0) == 1, debug&>::type operator<<(c i) {
        return * this << range(begin(i), end(i)); 
    }
    
    //   Part 3
    
    template < class c, class b > debug & operator << (pair < b, c > d) {
        return * this << "(" << d.first << ", " << d.second << ")";
    }
    
    //   Part 4
    
    template < class c > debug & operator <<(rge<c> d) {
        *this << "[";
        for (auto it = d.b; it != d.e; ++it)
            *this << ", " + 2 * (it == d.b) << *it;
        return * this << "]";
    }
    
};
#define qwer(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
ll dp[60][3000];
ll cambio[3000],tiempo[3000];
ll minglobal[3000];
struct nodo
{
    ll to,cost,time;
};
vector<nodo> g[3000];

int main()
{
    forr(i,0,55)
    {
        forr(j,0,2700)
            dp[i][j]=1e18;
        minglobal[i]=1e18;
    }
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m,s;
    cin>>n>>m>>s;
    ll iz,der,cost,time;
    forr(i,0,m)
    {
        cin>>iz>>der>>cost>>time;
        nodo e={der,cost,time};
        g[iz].pb(e);
        e={iz,cost,time};
        g[der].pb(e);
    }
    forr(i,1,n+1)
    {
        cin>>cambio[i]>>tiempo[i];
    }
    set<iii> cola;
    cola.insert(mp(0,mp(1,min(s,2500))));
    iii par;
    ll num,coins;
    ll newtime,newcoins;
    ll to,time2;
    
    while(!cola.empty())
    {
        auto ite=cola.begin();
        par=*ite;
        cola.erase(ite);
        if (dp[par.se.fi][par.se.se]<par.fi)
            continue;
        num=par.se.fi;
        coins=par.se.se;
        time=par.first;
        dp[num][coins]=time;
        forr(i,1,2601)
        {
            //c++;
            newcoins=coins+cambio[num]*i;
            if (newcoins>2500)break;
            newtime=time+tiempo[num]*i;
            if (dp[num][newcoins]>newtime)
            {
                dp[num][newcoins]=newtime;
                cola.insert({newtime,{num,newcoins}});
            }
            else
                break;
        }
        
        minglobal[num]=min(minglobal[num],time);
        forr(i,0,g[num].size())
        {
            to=g[num][i].to;
            cost=g[num][i].cost;
            time2=g[num][i].time;
            if (cost>coins)continue;
            newcoins=coins-cost;
            newtime=time+time2;
            if (dp[to][newcoins]>newtime)
            {
                dp[to][newcoins]=newtime;
                cola.insert({newtime,{to,newcoins}});
            }
        }
    }
    
    forr(i,2,n+1)
    {
        cout<<minglobal[i]<<"\n";
    }
}
// PLUS ULTRA!
    

Measured memory_bytes: 200268