#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  // 重み付き無向(有向)グラフの隣接リスト
  int n, m; // n:頂点数 m:辺数
  ll s;
  cin >> n >> m >> s;
  
  vector<vector<pair<int, pair<ll, ll>>>> G(n); // G:頂点数nのグラフの隣接リスト
  
  for (int i = 0; i < m; i++) {
    int u, v;
    ll a, b;
    cin >> u >> v >> a >> b;
    u--;
    v--;
    G[u].emplace_back(make_pair(v, make_pair(a, b)));
    G[v].emplace_back(make_pair(u, make_pair(a, b))); // 有向グラフではコメントアウト
  }
  
  vector<ll> c(n), d(n);
  for (int i = 0; i < n; i++) cin >> c.at(i) >> d.at(i);
  
  s = min<ll>(s, 2500);
  vector<vector<ll>> dp(n, vector<ll>(2501, 1e18));
  dp.at(0).at(s) = 0;
  
  priority_queue<tuple<ll, ll, int>, vector<tuple<ll, ll, int>>, greater<tuple<ll, ll, int>>> pq;
  pq.push(make_tuple(0, s, 0));
  while (!pq.empty()) {
    auto [time, silver, node] = pq.top();
    pq.pop();
    if (dp.at(node).at(silver) < time) continue;
    dp.at(node).at(silver) = time;
    if (silver < 2500) {
      ll keep = min<ll>(silver + c.at(node), 2500);
      if (dp.at(node).at(keep) > time + d.at(node)) {
        dp.at(node).at(keep) = time + d.at(node);
        pq.push(make_tuple(time + d.at(node), keep, node));
      }
    }
    for (int i = 0; i < G[node].size(); i++) {
      if (silver < G[node].at(i).second.first) continue;
      if (dp.at(G[node].at(i).first).at(silver - G[node].at(i).second.first) <= time + G[node].at(i).second.second) continue;
      dp.at(G[node].at(i).first).at(silver - G[node].at(i).second.first) = time + G[node].at(i).second.second;
      pq.push(make_tuple(time + G[node].at(i).second.second, silver - G[node].at(i).second.first, G[node].at(i).first));
    }
  }
  
  for (int i = 1; i < n; i++) {
    ll keep = 1e18;
    for (int j = 0; j <= 2500; j++) {
      keep = min(keep, dp.at(i).at(j));
    }
    cout << keep << '\n';
  }
}