#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int64, int> ii;
const int64 INF = 1LL << 60;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

const int N = 50;
const int M = 2500;
int64 dp[N * M];
struct Edge {
  int v, w, cost;
};
vector<Edge> a[N];
int c[N], d[N];

int main() {
  int n, m, rem;
  scanf("%d%d%d", &n, &m, &rem);
  rem = min(rem, M - 1);
  for (int i = 0; i < m; ++i) {
    int u, v, w, cost;
    scanf("%d%d%d%d", &u, &v, &cost, &w);
    --u; --v;
    a[u].push_back({v, w, cost});
    a[v].push_back({u, w, cost});
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &c[i], &d[i]);
  }
  fill(dp, dp + n * M, INF);
  priority_queue<ii, vector<ii>, greater<ii>> Q;
  dp[rem] = 0;
  Q.push({dp[rem], rem});
  while (!Q.empty()) {
    auto [dd, x] = Q.top();
    Q.pop();
    if (dd != dp[x]) continue;
    // trace(x, dd);
    int u = x / M, rem = x % M;
    // trace(u, rem, dp[x]);
    for (auto& [v, w, cost] : a[u]) {
      if (rem >= cost) {
        int nxt_x = v * M + rem - cost;
        if (dp[nxt_x] > dp[x] + w) {
          dp[nxt_x] = dp[x] + w;
          Q.push({dp[nxt_x], nxt_x});
        }
      }
      int nxt_x = u * M + min(rem + c[u], M - 1);
      if (dp[nxt_x] > dp[x] + d[u]) {
        dp[nxt_x] = dp[x] + d[u];
        Q.push({dp[nxt_x], nxt_x});
      }
    }
  }
  for (int i = 1; i < n; ++i) {
    int64 ret = INF;
    for (int j = 0; j < M; ++j) {
      ret = min(ret, dp[i * M + j]);
    }
    printf("%lld\n", ret);
  }
  return 0;
}


Measured memory_bytes: 6380