#include <bits/stdc++.h>

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 50;
const int MAX_M = 100;
const int MAX_MONEY = 2500;

int N, M, S;
struct E {
  E(int to = 0, int a = 0, int b = 0) : to(to), a(a), b(b) {}
  int to, a, b;
};
vector<E> edge[MAX_N];
int C[MAX_N];
int D[MAX_N];

int dist[MAX_N][MAX_MONEY+1];

struct P {
  P(int cost = 0, int pos = 0, int money = 0) : cost(cost), pos(pos), money(money) {}
  int cost;
  int pos, money;
  const bool operator < (const P& p) const {
    return cost < p.cost;
  }
  const bool operator > (const P& p) const {
    return cost > p.cost;
  }
};

signed main()
{
  cin >> N >> M >> S;
  S = min(S, MAX_MONEY);
  REP(m,M) {
    E e;
    int f, t, a, b;
    cin >> f >> t >> a >> b;
    f--; t--;
    edge[f].push_back(E(t,a,b));
    edge[t].push_back(E(f,a,b));
  }
  REP(n,N) {
    cin >> C[n] >> D[n];
  }

  REP(n,MAX_N) {
    REP(j,2501) {
      dist[n][j] = INF_LL;
    }
  }
  dist[0][S] = 0;

  priority_queue<P, vector<P>, greater<P>> pq;
  pq.push(P(0,0,S));
  while(pq.size()) {
    P p = pq.top(); pq.pop();
    if (dist[p.pos][p.money] < p.cost) continue;

    // お金の両替
    if (p.money + C[p.pos] <= MAX_MONEY) {
      if (dist[p.pos][p.money + C[p.pos]] > p.cost + D[p.pos]) {
        dist[p.pos][p.money + C[p.pos]] = p.cost + D[p.pos];
        pq.push(P(dist[p.pos][p.money + C[p.pos]], p.pos, p.money + C[p.pos]));
      }
    }

    // 移動
    for(E e : edge[p.pos]) {
      if (e.a <= p.money) {
        if (dist[e.to][p.money - e.a] > p.cost + e.b) {
          dist[e.to][p.money - e.a] = p.cost + e.b;
          pq.push(P(dist[e.to][p.money - e.a], e.to, p.money-e.a));
        }
      }
    }
  }

  FOR(i,1,N) {
    int ans = INF_LL;
    REP(n,MAX_MONEY+1) {
      ans = min(ans, dist[i][n]);
    }
    cout << ans << endl;
  }

  return 0;
}
