#include <iostream>
#include <fstream>
#include <algorithm>
#include <chrono>
#include <random>
#include <vector>
#include <string>
#include <cmath>
#include <bitset>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cassert>

#define sq(x) ((x) * (x))
#define err(x) cerr << "["#x"]  " << (x) << "\n";
#define errp(x) cerr << "["#x"]  {" << ((x).first) << ", " << ((x).second) << "}\n";
#define errv(x) {cerr << "["#x"]  [";for(const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
#define errvn(x, n) {cerr << "["#x"]  [";for(auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
#define errf() cerr << "\n\n";

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast, unroll-loops", "omit-frame-pointer","inline")
//#pragma GCC option("arch=native","tune=native","no-zero-upper")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native,avx2")

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getrnd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

ll getrndll(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

template <typename T1, typename T2>
inline bool relax(T1& a, const T2& b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

template <typename T1, typename T2>
inline bool strain(T1& a, const T2& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

// :::::::::::::::::::::::::::::::

struct ver {
    int v, coins;
    
    ver () {}
    ver(int a, int b) : v(a), coins(b) {}
};

struct edge {
    ll to, c, w;
    
    edge() {}
    edge(int x, int y, ll z) : to(x), c(y), w(z) {}
};

struct dist {
    ver to;
    ll w;
    
    dist() {}
    dist(ver x, ll y) : to(x), w(y) {}
};

bool operator <(const dist& a, const dist& b) {
    return a.w > b.w;
}

const int N = 53, M = 103, C = N * N + 3;
const ll INF = 1e18;

bool was[N][C];
ll d[N][C];
vector<edge> graph[N];

void solve() {
    int n, m, s;
    cin >> n >> m >> s;
    
    for (int i = 0; i < m; ++i) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        
        --x; --y;
        graph[x].emplace_back(y, a, b);
        graph[y].emplace_back(x, a, b);
    }
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        
        graph[i].emplace_back(i, -x, y);
    }
    
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < C; ++j)
            d[i][j] = INF;
    
    int stm = min(s, C - 1);
    priority_queue<dist> scope;
    
    d[0][stm] = 0;
    scope.push(dist(ver(0, stm), 0));
    while (true) {
        while (!scope.empty() && was[scope.top().to.v][scope.top().to.coins])
            scope.pop();
        if (scope.empty()) break;
        
        auto p = scope.top();
        scope.pop();
        
        int v = p.to.v, c = p.to.coins;
        
        was[v][c] = 1;
        for (auto e : graph[v]) {
            ll to = e.to, w = e.w, price = e.c;
            if (price <= c) {
                int tow = min(c - price, (ll)C - 1);
                if (relax(d[to][tow], d[v][c] + w))
                    scope.push(dist(ver(to, tow), d[to][tow]));
            }
        }
    }
    
    for (int i = 1; i < n; ++i) {
        ll mn = INF;
        for (int j = 0; j < C; ++j)
            relax(mn, d[i][j]);
        cout << mn << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    srand(time(0));
    
    int t = 1;
//    cin >> t;
    while (t--)
        solve();
    
    return 0;
}



Measured memory_bytes: 6656