# include <bits/stdc++.h>

using namespace std;

const int N = 55;
const int M = 2505;

int n, m, s;
int A[N], B[N], C[N], D[N];
long long f[N][M];
vector < pair <int, int> > g[N];

int main() {
    cin >> n >> m >> s;

    s = min(s, M - 1);

    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v >> A[i] >> B[i];
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }

    for (int i = 1; i <= n; i++) {
        cin >> C[i] >> D[i];
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            f[i][j] = 1e18;
        }
    }

    set < pair <long long, pair <int, int> > > st;

    for (int i = 0; i <= s; i++) {
        f[1][i] = 0;
    }
    
    st.insert({ f[1][s], {1, s} }); 

    while (!st.empty()) {
        int v = st.begin()->second.first, silver = st.begin()->second.second;
        st.erase(st.begin());
        if (silver + C[v] < M && f[v][silver] + D[v] < f[v][silver + C[v]]) {
            st.erase({ f[v][silver + C[v]], {v, silver + C[v]} });
            f[v][silver + C[v]] = f[v][silver] + D[v];
            st.insert({ f[v][silver + C[v]], {v, silver + C[v]} });
        }
        for (int i = 0; i < g[v].size(); i++) {
            int to = g[v][i].first, id = g[v][i].second;
            if (silver - A[id] >= 0 && f[v][silver] + B[id] < f[to][silver - A[id]]) {
                st.erase({ f[to][silver - A[id]], {to, silver - A[id]} });
                f[to][silver - A[id]] = f[v][silver] + B[id];
                st.insert({ f[to][silver - A[id]], {to, silver - A[id]} });
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        long long ans = 1e18;
        for (int j = 0; j < M; j++) {
            ans = min(ans, f[i][j]);
        }
        cout << ans << endl;
    }
}
