#include <bits/stdc++.h>
using namespace std;

class Debug {
private:
    static int NAME_LENGTH, MAX_WIDTH;
    static bool IS_MATRIX;
public:
    static void set_NAME_LENGTH(int l) { NAME_LENGTH = l; }
    static int get_NAME_LENGTH() { return NAME_LENGTH; }
    static void set_MAX_WIDTH(int w) { MAX_WIDTH = w; }
    static int get_MAX_WIDTH() { return MAX_WIDTH; }
    static void set_IS_MATRIX(bool f) { IS_MATRIX = f; }
    static bool get_IS_MATRIX() { return IS_MATRIX; }
};

int Debug::NAME_LENGTH = 0;
int Debug::MAX_WIDTH = 0;
bool Debug::IS_MATRIX = false;

// Debug for vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    bool flg = true;
    for (auto e : v) {
        os << (flg ? "" : ", ");
        if (Debug::get_IS_MATRIX()) {
            os << right << setw(Debug::get_MAX_WIDTH());
        }
        os << e;
        flg = false;
    }
    os << "]";
    return os;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    Debug::set_IS_MATRIX(true);
    int width = 0;
    for (unsigned int i = 0; i < v.size(); ++i) {
        for (unsigned int j = 0; j < v[i].size(); ++j) {
            width = max(width, (int)to_string(v[i][j]).size());
        }
    }
    Debug::set_MAX_WIDTH(width);
    string space = "";
    for (int i = 0; i < Debug::get_NAME_LENGTH() + 7; ++i) space += " ";
    os << "[";
    bool flg = true;
    for (auto e : v) {
        os << (flg ? "" : "\n" + space);
        os << e;
        flg = false;
    }
    os << "]";
    Debug::set_IS_MATRIX(false);
    return os;
}

// Debug for pair
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

// Debug for set
template <typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
    os << "{";
    bool flg = true;
    for (auto e : s) {
        os << (flg ? "" : ", ");
        os << e;
        flg = false;
    }
    os << "}";
    return os;
}

// Debug for map
template <typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& mp) {
    os << "{";
    bool flg = true;
    for (auto e : mp) {
        os << (flg ? "" : ", ");
        os << e.first << ": " << e.second;
        flg = false;
    }
    os << "}";
    return os;
}

// Debug assistant
#define DUMP(...) INTERNAL_DUMP(#__VA_ARGS__, __VA_ARGS__)

string REMOVE_SPACE(string s) {
    while (s[0] == ' ') {
        s = s.substr(1);
    }
    while (s[s.size() - 1] == ' ') {
        s = s.substr(0, s.size() - 1);
    }
    return s;
}

pair<string, string> GET_NAME(string s) {
    int bracket = 0, idx = 0;
    while ((unsigned)idx < s.size() && !(s[idx] == ',' && bracket == 0)) {
        if (s[idx] == '(') ++bracket;
        else if (s[idx] == ')') --bracket;
        ++idx;
    }
    string other_names;
    if ((unsigned)idx == s.size()) {
        other_names = "";
    } else {
        other_names = s.substr(idx + 1);
    }
    string first_name = s.substr(0, idx);
    first_name = REMOVE_SPACE(first_name);
    other_names = REMOVE_SPACE(other_names);
    return pair<string, string>(first_name, other_names);
}

// Debug main
void INTERNAL_DUMP(string name) {
    return;
}

template <class Head, class... Tail>
void INTERNAL_DUMP(string name, Head&& head, Tail&&... tail) {
    pair<string, string> p = GET_NAME(name);
    Debug::set_NAME_LENGTH(p.first.size());
    cerr << ">> " << p.first << " = " << head << endl;
	INTERNAL_DUMP(p.second, move(tail)...);
}

// End of Debug parts
//------------------------------------------------------------------------------

typedef pair<long long, int> P;

class edge0 {
public:
    int to, idx;
    edge0(int t, int i) {
        to = t;  idx = i;
    }
};

class edge {
public:
    int to, time;
    edge(int t, int tm) {
        to = t;  time = tm;
    }
};

int value(int v, int s) {
    return 2500 * v + s;
}

int main() {
    int N, M, S; cin >> N >> M >> S;
    vector<vector<edge0>> G0(N, vector<edge0>());
    vector<int> A(M), B(M);
    for (int i = 0; i < M; ++i) {
        int u, v;  cin >> u >> v >> A[i] >> B[i];
        --u;  --v;
        G0[u].push_back(edge0(v, i));
        G0[v].push_back(edge0(u, i));
    }
    vector<int> C(N), D(N);
    for (int i = 0; i < N; ++i) cin >> C[i] >> D[i];
    // DUMP("input end");

    // G の作成
    vector<vector<edge>> G(N * 2500, vector<edge>());
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 2499; ++j) {
            int to = min(value(i, j + C[i]), value(i, 2499));
            G[value(i, j)].push_back(edge(to, D[i]));
        }
        for (edge0 e : G0[i]) {
            for (int j = 0; j < 2500; ++j) {
                if (j - A[e.idx] >= 0) G[value(i, j)].push_back(edge(value(e.to, j - A[e.idx]), B[e.idx]));
            }
        }
    }
    // DUMP("graph end");

    // Dijkstra
    vector<long long> min_t(2500 * N);
    for (int i = 0; i < 2500 * N; ++i) min_t[i] = 1LL << 60;
    min_t[value(0, min(S, 2499))] = 0;
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, value(0, min(S, 2499))));
    while (!que.empty()) {
        P p = que.top();  que.pop();
        int i = p.second;
        if (min_t[i] < p.first) continue;
        for (edge e : G[i]) {
            if (min_t[e.to] > min_t[i] + e.time) {
                min_t[e.to] = min_t[i] + e.time;
                que.push(P(min_t[e.to], e.to));
            }
        }
    }

    for (int i = 1; i < N; ++i) {
        long long ans = 1LL << 60;
        for (int j = 0; j < 2500; ++j) {
            ans = min(ans, min_t[value(i, j)]);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 17520