#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>   
using namespace std;
using namespace __gnu_pbds;
typedef long long ll; 
#define int long long
typedef unsigned long long lu;
typedef vector<ll> v;
typedef vector<vector<ll> > vv;
typedef vector<string>  vs;
typedef vector<pair<ll,ll>> vpr;
typedef long double ld;
#define f(i,n) for(ll i = 0; i < n; i++)
#define ff(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define amax(x,y) if(y>x) x=y;
#define amin(x,y) if(y<x)x=y;
#define bg(x) x.begin()
#define sz(x) (ll)x.size()
#define in(x,n) for(ll i=0;i<n;i++)cin>>x[i]
#define out(x,n) for(ll i=0;i<n;i++)cout<<x[i]<<" " 
#define mxt(a) *(max_element(a.begin(),a.end()))
#define mnt(a) *(min_element(a.begin(),a.end())
#define tc ll t;cin>>t;while(t--)
typedef pair<ll,ll> pi;
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define yesno(f) if(f) yes else no
const v dx = {1, -1, 0, 0};
const v dy = {0, 0, 1, -1};
const ll mod=1e9+7;
const ld PI = 2 * acos(0.0);
ll m(ll a){ return (a+mod)%mod;}
ll cel(ll x1,ll y1){if((x1%y1)==0)return x1/y1;else return x1/y1+1;}
ll power(ll a,ll b,ll m)
{
    if(b==0)
        return 1;
    ll d=power(a,b/2,m);
    d=(d*d)%m;
    if(b&1)
        d=(d*a)%m;
    return d;
}
// set_name.find_by_order(k) It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time
// set_name.order_of_key(k) It returns to the number of items that are strictly smaller than our item k in O(logn) time.
/*string operations :
str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
str.substr (x) : returns a substring str[x],... end of string
str.find(qtr) : returns the first occurenece of qtr in str */
struct Tuple{
    int v1;
    int coins;
    int minutes;
};
void djistra(vector<vpr>&gr,int root,vector<int> &dist)
{
    int n=sz(dist);
    dist[root]=0;
    vector<bool>sptset(n,false);
    priority_queue<pair<int,int>,vpr,greater<pi> > que;
    que.push({0,root});
    while(!que.empty())
    {
        int u=que.top().second;
        que.pop();
        if(sptset[u])
            continue;
        sptset[u]=true;
        for(auto it:gr[u])
        {
            if(dist[it.first] > dist[u]+it.second)
            {
                dist[it.first]=dist[u]+it.second;
                que.push({dist[it.first],it.first});
            }
        }
    }
}
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n,m,s;cin>>n>>m>>s;

    vector<vector<Tuple> > gr(n);
    for(int i=0;i<m;i++)
    {
        int u1,v1;cin>>u1>>v1;
        u1--;
        v1--;
        int a,b;cin>>a>>b;
        Tuple p={v1,a,b},p2={u1,a,b};
        gr[u1].pb(p);
        gr[v1].pb(p2);
    }
    int A=50*n;
    s=min(s,A);
    int N=0;
    vv state(n,v(A+1));
    int root=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=A;j++)
        {
            if(i==0 && j==s)
            {
                root=N;
            }
            state[i][j]=N++;
        }
    
    }
    // v sinks;
    vector<vpr>gr2(N);
    for(int i=0;i<n;i++)
    {
        int c,d;cin>>c>>d;
        for(int j=0;j<=A;j++)
        {
            for(auto it:gr[i])
            {
                if(it.coins <= j)
                {
                    int new_coins=j-it.coins;
                    int wt=it.minutes;
                    int v1=state[it.v1][new_coins];
                    gr2[state[i][j]].pb({v1,wt});
                }
            }
            int new_coins=min(j+c,A);
            int wt=d;
            int v1=state[i][new_coins];
            gr2[state[i][j]].pb({v1,wt});
        }
    }
    vector<int>dist(N,1e18);
    djistra(gr2,root,dist);   
    vector<int>ans(n,1e18);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=A;j++)
        {
            int v1=state[i][j];
            ans[i]=min(ans[i],dist[v1]);       
        }
    }
    for(int i=1;i<n;i++)
        cout<<ans[i]<<"\n";    
    return 0;
}

Measured memory_bytes: 24688