#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>

using namespace std;

#define Rep(i,a,b) for(ll i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using ll = long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
    template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
    template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
    template<typename T> void chadd(T& a, T b) { a = a + b; }

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t sz;
        inp(std::size_t _sz = 1) : sz(_sz) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { std::vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
    };

    // 2次元用の標準入出力
    template<typename T>
    struct inpn {
        std::size_t szi, szj;
        inpn(std::size_t _szi, std::size_t _szj) : szi(_szi), szj(_szj) {}
        operator std::vector<std::vector<T>>() const {
            std::vector<std::vector<T>> a(szi, std::vector<T>(szj));
            for (std::size_t i = 0; i < szi; ++i)
                for (std::size_t j = 0; j < szj; ++j) cin >> a[i][j];
            return a;
        }
    };

    inp inp1; // input one

#define MAX_V 51 * 50LL

    struct edge {
        ll to;
        ll cost;
        ll money;
    };

    vector<edge> G[MAX_V];

    // ダイクストラ法
    vector<vector<ll>> dijkstra(ll start, ll init, ll n) {
        vector<vector<ll>> dist(n, vector<ll>(MAX_V, infll));
        rep(i, n) rep(j, MAX_V) dist[i][j] = infll;
        chmin(init, MAX_V - 1LL);
        dist[0][init] = 0; // dist[i] := start->iまでの最短距離

        priority_queue <edge, vector<edge>, function<bool(edge, edge)>> que(
            [](edge lhs, edge rhs) {
                return lhs.cost > rhs.cost;
            }
        );

        {
            edge e;
            e.to = start;
            e.cost = 0;
            e.money = init;
            que.push(e);
        }

        while (!que.empty()) {
            ll cost, u, money; // 今までにかかった時間　現在の頂点
            cost = que.top().cost;
            u = que.top().to;
            money = que.top().money;
            que.pop();

            if (dist[u][money] < cost) continue;
            for (auto tmp : G[u]) {
                ll v = tmp.to, time = tmp.cost, mon = -tmp.money; // 隣接する頂点、その頂点まで行く時間
                if (money + mon < 0 || money + mon >= MAX_V) continue;

                if (dist[v][money + mon] > dist[u][money] + time) {
                    dist[v][money + mon] = dist[u][money] + time;
                    edge e;
                    e.cost = dist[v][money + mon];
                    e.to = v;
                    e.money = money + mon;
                    que.push(e);
                }
            }
        }
        return dist;
    }

}

int main() {

    ll n, m, s;
    cin >> n >> m >> s;

    vector<ll> u(m), v(m), a(m), b(m);
    rep(i, m) {
        cin >> u[i] >> v[i] >> a[i] >> b[i];
    }
    vector<ll> c(n), d(n);
    rep(i, n) {
        cin >> c[i] >> d[i];
    }
    rep(i, m) {
        edge e;
        e.to = v[i] - 1;
        e.cost = b[i];
        e.money = a[i];
        G[u[i] - 1].push_back(e);
        e.to = u[i] - 1;
        G[v[i] - 1].push_back(e);
    }
    rep(i, n) {
        edge e;
        e.to = i;
        e.cost = d[i];
        e.money = -c[i];
        G[i].push_back(e);
    }

    // 拡張ダイクストラ法？
    auto dist = dijkstra(0, s, n);

    Rep(i, 1, n) {
        //cout << "to " << i << endl;
        ll ans = infll;
        rep(j, MAX_V) {
            //Cout(dist[i][j]);
            chmin(ans, dist[i][j]);
        }
        Cout(ans);
    }



    return 0;
}


Measured memory_bytes: 7372