#include <iostream>
#include <functional>
#include <algorithm>
#include <sstream>
#include <cstring>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <ctime>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define EPS 1e-8
#define LL_INF 0x3fffffffffffffff
#define INF 0x3f3f3f3f3f3f3f3f
#define MEM(a, b) memset(a, b, sizeof(a))
#define PPER(i, n, m) for (int i = n; i >= m; i--)
#define REPP(i, n, m) for (int i = n; i <= m; i++)
#define REP(i, n, m) for (int i = n; i < m; i++)
#define PER(i, n, m) for (int i = n; i > m; i--)
#define SA(n) scanf("%d", &(n))
#define SLLA(n) scanf("%lld", &(n))
#define MP make_pair
#define FF first
#define SS second
#define PB push_back
#define DE(val) cout << #val << ": " << val << endl;
 
const int dx44[6] = {0, -1, -1, 1, 1};
const int dy44[6] = {0, -1, 1, -1, 1};
const int dx4[6] = {0, 0, 1,-1};
const int dy4[6] = {1, -1, 0,0};
const int dx8[9] = {0, -1, 0, 1, 0, 1, 1, -1, -1};
const int dy8[9] = {0, 0, 1, 0, -1, 1, -1, 1, -1};
const int dx82[9] = {0, -1, -1, 1, 1, 2, 2, -2, -2};
const int dy82[9] = {0, 2, -2, 2, -2, 1, -1, 1, -1};

void update(ll& x,ll v){
    if(x==-1)x=v;
    else if(x>v)x=v;
}
 
ll po(ll a, ll b, ll mod)
{
    ll res = 1;
    a %= mod;
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
ll gcd(ll a, ll b)
{
    if (a == 0)
    {
        return b;
    }
    else
    {
        return gcd(b % a, a);
    }
}
void extgcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if (!b)
    {
        d = a;
        x = 1;
    }
    else
    {
        extgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}
ll inverse(ll a, ll n)
{
    ll d, x, y;
    extgcd(a, n, d, x, y);
    return d == 1 ? (x + n) % n : -1;
}
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const int maxn = 2e3 + 15;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
#define mst(x, a) memset(x, a, sizeof(x))
/*************************************************************************/

int n,m,s;
int u[maxn],v[maxn],a[maxn],b[maxn];
std::vector< pair< pair<int,int>, int> > edge[maxn];
int c[maxn], d[maxn];


ll dis[155][5555];


void solve() {
    SA(n);
    SA(m);
    SA(s);
    REPP(i,1,m) {
        SA(u[i]);
        SA(v[i]);
        SA(a[i]);
        SA(b[i]);
        edge[u[i]].push_back(MP(MP(a[i],b[i]), v[i]));
        edge[v[i]].push_back(MP(MP(a[i],b[i]), u[i]));
    }
    REPP(i,1,n) {
        SA(c[i]);
        SA(d[i]);
    }
    REPP(i,1,n) {
        REPP(k,0,5000) {
            dis[i][k] = 1e18;
        }
    }
    s = min(s, 5000);
    dis[1][s] = 0;
    priority_queue< pair<ll, pair<ll, ll>>, std::vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> que;
    que.push(MP(0 , MP(1, s)));

    while(!que.empty()) {
        auto now = que.top();
        que.pop();

        ll dis_t = now.first;
        ll pos = now.second.first;
        ll cost = now.second.second;

        REP(i,0,edge[pos].size()) {
            int nxt = edge[pos][i].second;
            int edge_cost = edge[pos][i].first.first;
            int edge_dis = edge[pos][i].first.second;
            
            if(cost >= edge_cost) {
                if(dis[nxt][cost-edge_cost] > dis_t + edge_dis) {
                    dis[nxt][cost-edge_cost] = dis_t + edge_dis;
                    
                    que.push(MP(dis_t + edge_dis, MP(nxt, cost-edge_cost)));
                }
            }
        }
        if(cost + c[pos] <= 5000) {
            if(dis[pos][cost + c[pos]] > dis_t + d[pos]) {
                
                dis[pos][cost + c[pos]] = dis_t + d[pos];
                que.push(MP(dis_t + d[pos], MP(pos, cost + c[pos])));
            }
        }
    }

    REPP(i,2,n) {
        ll ans = 1e18;
        REPP(k,0,5000) {
            ans = min(ans, dis[i][k]);
        }
        printf("%lld\n", ans);
    }
}
int main()
{   
#ifndef ONLINE_JUDGE
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
#endif

    solve();
    // int t;
    // SA(t);
    // REPP(i,1,t) {
    //     printf("Case #%d: ", i);
    //     solve();
    // }
    return 0;
 
}
 

Measured memory_bytes: 11296