#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(),(x).end()
#define lowbit(x) x&-x
#define pb push_back
#define ls (id<<1)
#define rs (id<<1|1)
#define Rint register int
#define UNI(x) sort(ALL(x)),x.resize(unique(ALL(x))-x.begin())
#define GETPOS(c,x) (lower_bound(ALL(c),x)-c.begin())
#define LEN(x) strlen(x)
#define MS0(x) memset((x),0,sizeof((x)))
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<pii> Vpii;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(ll &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const ll &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
const int MAXN=1e6+10,MAXM=4e6+10;
const int INF=INT_MAX,SINF=0x3f3f3f3f;
const ll llINF=LLONG_MAX;
const int MOD=1e9+7,mod=998244353;
const int inv2=5e8+4;
const int Lim=1<<20;

ll dp[55][5555],t[MAXN];
ll n,m,s,c[MAXN],a[MAXN],b[MAXN];
ll head[MAXN],to[MAXN],_next[MAXN],ecnt;

void add_Edge(int u,int v,int ti,int co)
{
    _next[++ecnt]=head[u];
    to[ecnt]=v;
    t[ecnt]=ti;
    c[ecnt]=co;
    head[u]=ecnt;
}

struct Node
{
    ll u,c,t;
    bool operator < (const Node&rhs)const
    {
        return t>rhs.t;
    }
};

priority_queue<Node> pq;

void bfs()
{
    memset(dp,0x3f,sizeof(dp));
    s=min(s,2500ll);
    dp[1][s]=0;
    pq.push({1,s,0});
    while(!pq.empty())
    {
        Node tmp=pq.top();pq.pop();
        if(dp[tmp.u][min(tmp.c+a[tmp.u],2500ll)]>dp[tmp.u][tmp.c]+b[tmp.u])
        {
            dp[tmp.u][min(tmp.c+a[tmp.u],2500ll)]=dp[tmp.u][tmp.c]+b[tmp.u];
            pq.push({tmp.u,min(tmp.c+a[tmp.u],2500ll),dp[tmp.u][min(tmp.c+a[tmp.u],2500ll)]});
        }
        for(int i=head[tmp.u];i;i=_next[i])
        {
            int v=to[i];
            if(tmp.c<c[i])continue;
            if(dp[v][tmp.c-c[i]]>dp[tmp.u][tmp.c]+t[i])
            {
                dp[v][tmp.c-c[i]]=dp[tmp.u][tmp.c]+t[i];
                pq.push({v,tmp.c-c[i],dp[v][tmp.c-c[i]]});
            }
        }
    }
}

void solve()
{
    R(n,m,s);
    for(int i=1;i<=m;i++)
    {
        int u,v,aa,bb;
        R(u,v,aa,bb);
        add_Edge(u,v,bb,aa);
        add_Edge(v,u,bb,aa);
    }
    for(int i=1;i<=n;i++)R(a[i],b[i]);
    bfs();
    for(int i=2;i<=n;i++)
    {
        ll ans=llINF;
        for(int j=0;j<=2500;j++)ans=min(ans,dp[i][j]);
        W(ans);
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
	int t=1;
	//R(t);
	while(t--)solve();
	return 0;
}


Measured memory_bytes: 8828