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

struct edge {
  long long time;
  long long cost;
  int to;
};
struct item {
  long long time;
  int cur;
  long long num;
  bool operator>(const item& rhs) const {
    return time > rhs.time;
  }
};
struct change {
  long long rate;
  long long time;
};

int main() {
  long long n, m, s;
  cin>>n>>m>>s;
  vector<edge> g[n];
  for (int i=0; i<m; i++) {
    int u, v, a, b;
    cin>>u>>v>>a>>b;
    --u;
    --v;
    g[u].push_back({b, a, v});
    g[v].push_back({b, a, u});
  }
  change c[n];
  for (int i=0; i<n; i++) cin>>c[i].rate>>c[i].time;

  long long d[n][2501];
  bool used[n][2501];
  for (int i=0; i<n; i++) {
    for (int j=0; j<2501; j++) {
      d[i][j] = 1e12;
      used[i][j] = false;
    }
  }
  s = min(s, 2500LL);
  priority_queue<item, vector<item>, greater<item>> pq;
  pq.push({0LL, 0, s});
  d[0][s] = 0;
  while (!pq.empty()) {
    auto top = pq.top();
    pq.pop();
    long long time = top.time;
    int cur = top.cur;
    long long num = top.num;
    if (used[cur][num]) continue;
    used[cur][num] = true;
    long long time2 = time + c[cur].time;
    long long num2 = num + c[cur].rate;
    if (num2 <= 2500 && !used[cur][num2]) {
      if (time2 < d[cur][num2]) {
        d[cur][num2] = time2;
        pq.push({time2, cur, num2});
      }
    }
    for (auto e: g[cur]) {
      long long e_time = e.time;
      long long e_cost = e.cost;
      int e_to = e.to;
      long long to_num = num - e_cost;
      long long to_time = time + e_time;
      if (to_num < 0 || used[e_to][to_num]) continue;
      if (to_time < d[e_to][to_num]) {
        d[e_to][to_num] = to_time;
        pq.push({to_time, e_to, to_num});
      }
    }
  }
  for (int i=1; i<n; i++) {
    long long ans = 1e12;
    for (int j=0; j<2501; j++) {
      ans = min(d[i][j], ans);
    }
    cout<<ans<<endl;
  }
}
