#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

template<typename T1,typename T2> inline void chmin(T1 &a, T2 b){ if(a > b) a = b; }
template<typename T1,typename T2> inline void chmax(T1 &a, T2 b){ if(a < b) a = b; }

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
const int MAX_N = 100010;

// 頂点倍化ダイクストラ
// 各頂点が state 個の状態をもつ場合、頂点数が V * state 個になる
class Dijkstra {
    public:
        // コンストラクタ
        // v … 頂点数, state … 各頂点がもつ状態の数 [0, state), inf: …「無限大」とする値
        Dijkstra() {}
        Dijkstra(int v, int state) { Init(v, state, LLINF); }
        Dijkstra(int v, int state, int inf) { Init(v, state, inf); }
        void Init(int v, int state) { Init(v, state, LLINF); }
        void Init(int v, int state, int inf) {
            assert(v > 0);
            assert(state > 0);
            m_N = v;
            m_State = state;
            m_MulN = m_N * m_State;
            m_Inf = inf;
            m_Graph.assign(m_MulN, vector< pair<int, int> >());
        }
        // 有向辺の追加。負のコストは未対応
        void AddDirEdge(int from_node, int from_state, int to_node, int to_state, int cost) {
            assert(0 <= from_node && from_node < m_N);
            assert(0 <= to_node && to_node < m_N);
            assert(0 <= from_state && from_state < m_State);
            assert(0 <= to_state && to_state < m_State);
            int from = from_node * m_State + from_state;
            int to = to_node * m_State + to_state;
            m_Graph[from].push_back(make_pair(to, cost));
        }
        // 無向辺の追加。負のコストは未対応
        // 状態ありの場合はホントに無向辺で追加できるか確認した方がいい(いけない場合がある)
        void AddUndirEdge(int from_node, int from_state, int to_node, int to_state, int cost) {
            AddDirEdge(from_node, from_state, to_node, to_state, cost);
            AddDirEdge(to_node, to_state, from_node, from_state, cost);
        }
        // 始点 s , 状態 s_state から各頂点への最短経路の導出 O(E log V)
        void Calc(int s, int s_state) {
            assert(0 <= s && s < m_N);
            assert(0 <= s_state && s_state < m_State);
            m_Dist.assign(m_MulN, m_Inf);
            m_PrevP.assign(m_MulN, -1);
            // 最短距離が短い順で cand を取り出す
            // pair<int, int> 小さい順の priority_queue(間に vector を入れないと昇順にならない)
            // この pair は (first: second 到達までのコスト, second: 頂点id)
            priority_queue<pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > cand;
            s = s * m_State + s_state;
            m_Dist[s] = 0;  // 始点のコストは 0
            cand.push(make_pair(0, s));
            while(!cand.empty()) {
                pair<int, int> p = cand.top(); cand.pop();     // cand のトップを取り出す
                int v = p.second;
                // 頂点 v まで最短経路が、 cand から取り出したものより既に小さいなら何もしない
                if(m_Dist[v] < p.first){ continue; }
                // 現在見ている頂点から延びている辺を全て見る
                for(const auto& e : m_Graph[v]) {
                    int next_node = e.first;    // 次行くとこ
                    int cost = e.second;        // v -> next_node のコスト
                    if(m_Dist[next_node] > m_Dist[v] + cost) {
                        // 現在の最短経路より短くなるなら更新
                        m_Dist[next_node] = m_Dist[v] + cost;
                        m_PrevP[next_node] = v;
                        cand.push(make_pair(m_Dist[next_node], next_node));
                    }
                }
            }
        }
        // 始点 s の状態 s_state から頂点 t の状態 t_state への最短距離を返す O(1)
        // 前処理として Calc(s, s_state) が必要
        int GetDist(int t, int t_state) { return m_Dist[t * m_State + t_state]; }
        // 始点 s の状態 s_state から頂点 t の状態 t_state までの経路を vector に入れて返す (s と t 含む)
        // O(V') … V' は最短経路の頂点数
        // 前処理として Calc(s, s_state) が必要
        vector< pair<int, int> > GetPath(int t, int t_state) {
            vector< pair<int, int> > path;
            t = t * m_State + t_state;
            for(; t != -1; t = m_PrevP[t]) {
                path.push_back(make_pair(t / m_State, t % m_State));
            }  // t が s になるまで prev_p[t] を辿っていく
            // このままだと t->s の順になっているので逆順にする
            reverse(path.begin(), path.end());
            return path;
        }
    private:
        int m_N;                    // 倍化前の頂点の数
        int m_MulN;                 // 倍化後の頂点の数( = 元の頂点の数 * 状態の数)
        int m_State;                // 状態の数
        int m_Inf;                  // 無限の代わりとして扱う値
        // 頂点 i から延びている辺の vector(隣接リスト) first: 行先 second: コスト
        vector< vector< pair<int, int> > > m_Graph;
        vector<int> m_Dist;         // 各頂点への最短コスト。つまり答え
        vector<int> m_PrevP;        // 最短経路の各頂点を保存(経路復元で利用)
};

const int MAX_STATE = 2600;

int N, M, S;
vector< vector< tuple<int, int, int> > > graph;     // 0: 行先, 1: 運賃(a), 2: コスト(b)
vector< pair<int, int> > CD;                        // first: 交換銀貨枚数(c), second: コスト(d)

signed main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M >> S;

    graph.assign(N, vector< tuple<int, int, int> >());
    REP(i, M) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--; v--;
        graph[u].push_back(make_tuple(v, a, b));
        graph[v].push_back(make_tuple(u, a, b));
    }
    REP(i, N) {
        int c, d;
        cin >> c >> d;
        CD.push_back(make_pair(c, d));
    }

    Dijkstra dk(N, MAX_STATE);

    // 金貨→銀貨の遷移を追加
    REP(i, N) {
        REP(j, MAX_STATE - CD[i].first) {
            int next_j = j + CD[i].first;
            if(next_j >= MAX_STATE) { next_j = MAX_STATE - 1; }
            dk.AddDirEdge(i, j, i, next_j, CD[i].second);
        }
    }

    // 他ノードへの遷移を追加
    REP(i, N) {
        for(auto& tmp : graph[i]) {
            int next_node = get<0>(tmp);
            int a = get<1>(tmp);
            int b = get<2>(tmp);
            REP(j, MAX_STATE) {
                if(j - a >= 0) {
                    dk.AddDirEdge(i, j, next_node, j - a, b);
                }
            }
        }
    }

    if(S >= MAX_STATE) { S = MAX_STATE - 1; }
    dk.Calc(0, S);

    for(int i = 1; i < N; ++i) {
        int ans = LLINF;
        REP(j, MAX_STATE) {
            chmin(ans, dk.GetDist(i, j));
        }
        printf("%lld\n", ans);
    }

    return 0;
}



Measured memory_bytes: 25440