#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<ll,ll> P;
constexpr ll INF = (1LL << 55);

int main(){ 
  int n, m, s;
  cin >> n >> m >> s;
  vector<vector<pair<int,P>>> g(n);
  rep(i,m) {
    int u, v, 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);
  rep(i,n) cin >> c[i] >> d[i];
  const int CMAX = m * 50;
  s = min(s, CMAX);
  for (int i = 0; i < n; i++) {
    vector<ll> time(CMAX + 1, -1);
    for (int j = 1; c[i] * j <= CMAX; j++) {
      time[j] = d[i] * j; 
    } 
    for (auto e : g[i]) {
      int v = e.first;
      ll a = e.second.first, b = e.second.second;
      for (int j = 1; c[i] * j <= CMAX; j++) {
        g[i].emplace_back(make_pair(v, make_pair(c[i] * j + a, time[j] + b)));
      }
    }
  }

  auto dijkstra = [&](int first = 0){
    vector<vector<ll>> dp(n, vector<ll>(CMAX + 1,INF));
    priority_queue<pair<ll, pair<int,int>>, vector<pair<ll, pair<int,int>>>, greater<pair<ll, pair<int,int>>>> que;
    dp[first][s] = 0;
    que.push(make_pair(0, make_pair(first, s)));
    while (!que.empty()) {
      auto p = que.top();
      que.pop();
      int u = p.second.first;
      int now = p.second.second;
      if (dp[u][now] < p.first) continue;
      for (auto e : g[u]) {
        int v = e.first;
        int next = now + e.second.first;
        ll cost = e.second.second;
        if (next < 0 || next > CMAX) continue;
        if (dp[v][next] > dp[u][now] + cost) {
          dp[v][next] = dp[u][now] + cost;
          que.push(make_pair(dp[v][next], make_pair(v, next)));
        }
      }
    }
    return dp;
  };
  auto res = dijkstra();
  for (int i = 1; i < n; i++) {
    ll ans = INF;
    for (int j = 0; j <= CMAX; j++) {
      ans = min(ans, res[i][j]);
    }
    cout << ans << endl;
  }
  return 0;
} 