/**
 *     author: qodjf
 *     created: 04.28.2020 00:54:41
 */
#include <bits/stdc++.h>
using namespace std;

string to_string(string s) { return '"' + s + '"'; }

string to_string(const char *s) { return to_string((string)s); }

string to_string(bool b) { return (b ? "true" : "false"); }

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifndef ONLINE_JUDGE
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

#define mst(x, a) memset(x, a, sizeof(x))

using ll = long long;
using P = pair<int, int>;
using T = tuple<ll, int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LLINF = 0x3f3f3f3f3f3f3f3f;
constexpr ll MOD = 1e9 + 7;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct edge {
  int to, cost, t;
  edge(int _to, int _cost, int _time) : to(_to), cost(_cost), t(_time) {}
};

int N, M, S;
int maxCoinsNeeded;
vector<vector<edge>> g;
ll dis[50][10010];

void solve() {
  mst(dis, INF);
  S = min(S, maxCoinsNeeded);
  dis[0][S] = 0;
  priority_queue<T, vector<T>, greater<T>> que;
  que.emplace(0, 0, S);
  while (!que.empty()) {
    auto p = que.top();
    que.pop();
    ll spendT = get<0>(p);
    int pos = get<1>(p), coin = get<2>(p);
    if (spendT > dis[pos][coin]) continue;
    for (const edge &e : g[pos]) {
      int v = e.to;
      int nCoin = min(coin - e.cost, maxCoinsNeeded);
      ll nT = spendT + e.t;
      if (nCoin >= 0 && nT < dis[v][nCoin]) {
        dis[v][nCoin] = nT;
        que.emplace(nT, v, nCoin);
      }
    }
  }

  for (int i = 1; i < N; i++) {
    cout << *min_element(dis[i], dis[i] + maxCoinsNeeded + 1) << endl;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> N >> M >> S;
  g.resize(N);
  maxCoinsNeeded = 0;
  for (int i = 0; i < M; i++) {
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    u--, v--;
    g[u].emplace_back(v, a, b);
    g[v].emplace_back(u, a, b);
    maxCoinsNeeded += 2 * a;
  }
  for (int i = 0; i < N; i++) {
    int c, d;
    cin >> c >> d;
    g[i].emplace_back(i, -c, d);
  }
  solve();
}
