#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;
template <typename T1, typename T2>
inline void chmin(T1 &a, const T2 &b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &a, const T2 &b) {
  if (a < b) a = b;
}
template <typename T>
vector<T> dijkstra(vector<vector<pair<int, T>>> &g, int s) {
  int n = g.size();
  const auto inf = numeric_limits<T>::max();
  vector<T> dist(n, inf);
  using P = pair<T, int>;
  priority_queue<P, vector<P>, greater<P>> que;
  dist[s] = 0;
  que.emplace(dist[s], s);
  while (!que.empty()) {
    T cost;
    int node;
    tie(cost, node) = que.top();
    que.pop();
    if (dist[node] < cost) continue;
    for (auto &e : g[node]) {
      auto next_cost = cost + e.second;
      int next_node = e.first;
      if (dist[next_node] <= next_cost) continue;
      dist[next_node] = next_cost;
      que.emplace(next_cost, next_node);
    }
  }
  return dist;
}
struct info {
  int a, b;
  info(int a, int b) : a(a), b(b) {}
  info() {}
};
int main() {
  const lint maxGold = 2600;
  lint toNode[51][2602];
  lint n, m, s;
  cin >> n >> m >> s;
  s = min(s, maxGold);
  int node = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= maxGold; j++) {
      toNode[i][j] = node;
      node++;
    }
  }
  vector<vector<pair<int, info>>> g(n);
  for (int i = 0; i < m; i++) {
    lint u, v, a, b;
    cin >> u >> v >> a >> b;
    u--;
    v--;
    g[u].push_back({v, info(a, b)});
    g[v].push_back({u, info(a, b)});
  }
  vector<lint> c(n);
  vector<lint> d(n);
  for (int i = 0; i < n; i++) {
    cin >> c[i] >> d[i];
  }
  vector<vector<pair<int, lint>>> gg(node);
  lint S = toNode[0][s];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < maxGold; j++) {
      int cur = toNode[i][j];
      lint nxtG = j + c[i];
      nxtG = min(nxtG, maxGold);
      int nxt = toNode[i][nxtG];
      lint cost = d[i];
      gg[cur].push_back({nxt, cost});
    }
  }
  for (int u = 0; u < n; u++) {
    for (int j = 0; j <= maxGold; j++) {
      for (auto e : g[u]) {
        int v = e.first;
        lint a = e.second.a;
        lint b = e.second.b;
        int cur = toNode[u][j];
        if (j < a) continue;
        int nxt = toNode[v][j - a];
        lint cost = b;
        gg[cur].push_back({nxt, cost});
      }
    }
  }
  auto dist = dijkstra(gg, S);
  for (int to = 1; to < n; to++) {
    lint ans = INF;
    for (int j = 0; j <= maxGold; j++) {
      int cur = toNode[to][j];
      ans = min(ans, dist[cur]);
    }
    cout << ans << endl;
  }
  return 0;
}
