#include <bits/stdc++.h>

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 110; //点数
const i64 INF = 0x3f3f3f3f3f3f3f3fLL;
struct node {
    int id, w, money;  // w == distance
    node(){}
    node(int a, int b, int c) : id(a), w(b), money(c) {}
    friend bool operator < (node a, node b) {return a.w > b.w;}
};
vector<node> G[maxn];
i64 dp[55][3050], a[maxn], b[maxn], c[maxn], d[maxn];
i64 n, m, s;

void dij(int start, int n) {
    for (int i = 0; i <= 50; ++i) {
        for (int j = 0; j <= 3000; ++j) {
            dp[i][j] = INF;
        }
    }
    priority_queue<node> q;
    node cur;
    q.push(node(start, 0, s));
    dp[start][s] = 0;
    while (!q.empty()) {
        cur = q.top();
        q.pop();
        int u = cur.id;
        int temp = cur.money+c[u];
        temp = min(temp, 3000);
        if (dp[u][temp] > dp[u][cur.money]+d[u]) {
            dp[u][temp] = dp[u][cur.money]+d[u];
            q.push(node(u, dp[u][temp], temp));
        }
        for (node to : G[cur.id]) {
            if (cur.money >= to.money
                && dp[to.id][cur.money-to.money] > dp[cur.id][cur.money]+to.w) {
                dp[to.id][cur.money-to.money] = dp[cur.id][cur.money]+to.w;
                q.push(node(to.id, dp[to.id][cur.money-to.money], cur.money-to.money));
            }
        }
    }
}
void init(int n) {
    for (int i = 0; i <= n; ++i) G[i].clear();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif

    cin >> n >> m >> s;
    s = min(s, 3000LL);
    init(n);
    forn(i, m) {
        int u, v;
        cin >> u >> v >> a[i] >> b[i];
        G[u].eb(node(v, b[i], a[i]));
        G[v].eb(node(u, b[i], a[i]));
    }
    for1(i, n) cin >> c[i] >> d[i];
    dij(1, n);
    for (int i = 2; i <= n; ++i) {
        i64 ans = LLONG_MAX;
        for (int j = 0; j <= 3000; ++j) {
            ans = min(ans, dp[i][j]);
        }
        cout << ans << '\n';
    }

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}
