#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

struct Edge {
  ll t, c, m;

  bool operator < (const Edge& e) const {
    return m > e.m;
  }
};

vector<Edge> G[55];

vector<vector<ll>> dp(55, vector<ll>(2505, INF));

void dijkstra(ll s) {
  repr(i, s) dp[0][s] = 0;
  priority_queue<pair<Edge, ll>> pq;
  pq.push({{0, 0, 0}, s});
  while (!pq.empty()) {
    ll v = pq.top().first.t, resc = pq.top().second;
    pq.pop();
    for (Edge e: G[v]) {
      ll nxtc = resc - e.c;
      if (nxtc < 0) continue;
      chmin(nxtc, 2500LL);
      if (chmin(dp[e.t][nxtc], dp[v][resc] + e.m)) {
        pq.push({e, nxtc});
        repr(i, nxtc - 1) {
          if (!chmin(dp[e.t][i], dp[v][resc] + e.m)) break;
        }
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ll n, m, s;
  cin >> n >> m >> s;
  chmin(s, 2500LL);
  rep(i, m) {
    ll u, v, a, b;
    cin >> u >> v >> a >> b;
    u--, v--;
    G[u].push_back({v, a, b});
    G[v].push_back({u, a, b});
  }
  rep(i, n) {
    ll c, d;
    cin >> c >> d;
    G[i].push_back({i, -c, d});
  }
  dijkstra(s);
  FOR(i, 1, n) cout << dp[i][0] << '\n';







  
  return 0;
}