#include <bits/stdc++.h>
using namespace std;
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec) is >> x;
  return is;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "{";
  for (int i = 0; i < (int)vec.size(); i++)
    os << vec[i] << (i + 1 == (int)vec.size() ? "" : ", ");
  os << "}";
  return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, map<T, U> &map_var) {
  os << "{";
  for (auto &&itr : map_var) {
    os << *itr;
    itr++;
    if (itr != map_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &set_var) {
  os << "{";
  for (auto &&itr : set_var) {
    os << *itr;
    itr++;
    if (itr != set_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
void dump_func() { cerr << endl; }
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&...tail) {
  cerr << head;
  if (sizeof...(Tail) > 0) cerr << ", ";
  dump_func(std::move(tail)...);
}
using namespace std;
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
using vec = std::vector<T>;
template <class T>
void print(const T &x) {
  cout << x << "\n";
}
const long long MOD = 1000000007, INF0 = 1061109567, INF = INF0 * INF0;
const double EPS = 1e-7, PI = acos(-1.0);
const long long dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
struct info {
  long long u, v, a, b;
};
struct edge {
  long long to, cost;
};
vec<edge> G[300000];
vec<info> arr;
long long d[300000];
long long cc[60];
long long dd[60];
long long maxA = 0;
long long vertexID(long long v, long long num) { return v * (maxA + 1) + num; }
void dijkstra(long long s) {
  priority_queue<pair<long long, long long>, vec<pair<long long, long long> >,
                 greater<pair<long long, long long> > >
      que;
  fill(d, d + 300000, INF);
  d[s] = 0;
  que.push(pair<long long, long long>(d[s], s));
  while (!que.empty()) {
    pair<long long, long long> p = que.top();
    que.pop();
    long long v = p.second;
    if (d[v] < p.first) {
      continue;
    }
    for (auto &&e : G[v]) {
      bool p = chmin(d[e.to], d[v] + e.cost);
      if (p) {
        que.push(pair<long long, long long>(d[e.to], e.to));
      }
    }
  }
}
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  long long N, M, S;
  cin >> N >> M >> S;
  for (long long i = 0; i < M; i++) {
    info ret;
    cin >> ret.u >> ret.v >> ret.a >> ret.b;
    ret.u--, ret.v--;
    chmax(maxA, ret.a);
    arr.push_back(ret);
  }
  maxA *= N - 1;
  if (S >= maxA) S = maxA;
  for (long long i = 0; i < M; i++) {
    info ele = arr[i];
    long long u = ele.u;
    long long v = ele.v;
    long long a = ele.a;
    long long b = ele.b;
    for (long long j = 0; j < maxA; j++) {
      if (j + a <= maxA) {
        long long j0 = j;
        long long j1 = j + a;
        G[vertexID(u, j1)].push_back(edge{vertexID(v, j0), b});
        G[vertexID(v, j1)].push_back(edge{vertexID(u, j0), b});
      }
    }
  }
  for (long long i = 0; i < N; i++) {
    cin >> cc[i] >> dd[i];
  }
  for (long long i = 0; i < N; i++) {
    for (long long j = 0; j < maxA; j++) {
      long long j0 = j;
      long long j1 = j + cc[i];
      G[vertexID(i, j0)].push_back(edge{vertexID(i, min(j1, maxA)), dd[i]});
    }
  }
  dijkstra(vertexID(0, S));
  for (long long i = 1; i <= N - 1; i++) {
    long long ans = INF;
    for (long long j = 0; j <= maxA; j++) {
      chmin(ans, d[vertexID(i, j)]);
    }
    print(ans);
  }
}
