#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

/*
    Dijkstra's Algorithm (Single Source Shortest Path) O(|E|logV)
        - for directed graph
        - NO edges have negative cost
        - 0-indexed vertexes
 */

class Dijkstra {
    private:
        vector< vector<LLP> > G;
        vector<ll> cost;
        vector<ll> par;
        priority_queue<LLP, vector<LLP>, greater<LLP> > que;

    public:
        Dijkstra(ll n, vector<vector<ll>> g, ll s);
        ll  getCost(ll target);
        vector< vector<ll> > getPath(ll  target);
};

// n: |V|
// g: [point_from, point_to, cost] (directed graph)
// s: start point
Dijkstra::Dijkstra(ll n, vector<vector<ll>> g, ll s) {
    for (ll  i = 0; i < n; i++) {
        G.push_back(vector<LLP>());
        cost.push_back(-1);
        par.push_back(-1);
    }

    // create adj-Graph
    for (ll i = 0; i < g.size(); i++) {
        G[g[i][0]].push_back(make_pair(g[i][1], g[i][2]));
    }

    // initialize
    cost[s] = 0;
    par[s] = s;
    que.push(make_pair(cost[s], s));

    while (!que.empty()) {
        LLP p = que.top();
        que.pop();

        if (cost[p.second] < p.first) continue;
        for (int i = 0; i < G[p.second].size(); i++) {
            if (cost[G[p.second][i].first] < 0 || cost[G[p.second][i].first] > cost[p.second] + G[p.second][i].second) {
                cost[G[p.second][i].first] = cost[p.second] + G[p.second][i].second;
                par[G[p.second][i].first] = p.second;
                que.push(make_pair(cost[G[p.second][i].first], G[p.second][i].first));
            }
        }
    }
}

// returns the minimum cost from the start point to the target.
// (if there is no path to the target, this returns -1.)
// (if the target is the start point, this returns 0.)
ll Dijkstra::getCost(ll target) {
    return cost[target];
}


// returns a list of path: Array of [point_from, point_to, cost].
// (if there is no path to the target or the target is the start point, this returns an empty vector.)
vector< vector<ll> > Dijkstra::getPath(ll target) {

    vector< vector<ll> > reversePath = vector< vector<ll> >(0);

    if (cost[target] <= 0) return reversePath;
    
    ll now_p = target;
    while (par[now_p] != now_p) {
        vector<ll> temp(3);
        temp[0] = par[now_p];
        temp[1] = now_p;
        temp[2] = cost[now_p] - cost[par[now_p]];
        reversePath.push_back(temp);
        now_p = par[now_p];
    }

    vector< vector<ll> > path = vector< vector<ll> >(0);
    for (ll i = reversePath.size() - 1; i >= 0; i--) path.push_back(reversePath[i]);

    return path;
}

ll Amax = 0;
ll coinMax = 0;
ll N, M, S;
ll getV(ll i, ll j) {
  return (coinMax + 1) * i + j;
}

int main() {
  
  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];
    U[i]--; V[i]--;
  }
  vector<ll> C(N), D(N);
  rep(i,N) {
    cin >> C[i] >> D[i];
  }

  rep(i,M) Amax = max(Amax, A[i]);
  coinMax = Amax * (N - 1);

  vector<vector<ll>> edges;
  rep(i,N) {
    rep(j,coinMax) {
      vector<ll> e(3);
      e[0] = getV(i, j);
      e[1] = getV(i, min(j + C[i], coinMax));
      e[2] = D[i];
      edges.push_back(e);
    }
  }
  rep(k,M) {
    for (ll j = A[k]; j <= coinMax; j++) {
      vector<ll> e(3);
      e[0] = getV(U[k], j);
      e[1] = getV(V[k], j - A[k]);
      e[2] = B[k];
      edges.push_back(e);
      e[0] = getV(V[k], j);
      e[1] = getV(U[k], j - A[k]);
      e[2] = B[k];
      edges.push_back(e);
    }
  }

  S = min(S, coinMax);
  Dijkstra tree(N * (coinMax + 1), edges, getV(0, S));
  rep(i,N) {
    if (i == 0) continue;
    ll ans = LINF;
    rep(j,coinMax) {
      if (tree.getCost(getV(i, j)) == -1) continue;
      ans = min(ans, tree.getCost(getV(i, j)));
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 91224