#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include<limits>
#include<iomanip>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const long double pi = 3.141592653589793;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repi(i, j, n) for(int i = j;i < n;i++)
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define F first
#define S second

// #define COMMENT

/*

const int NN = 200090;
ll fact[NN];
ll finv[NN];
ll inv[NN];

void inverse_modulao() {
  fact[0] = fact[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;

  for(int i = 2;i < NN;i++) {
    fact[i] = fact[i-1]*i%mod;
    inv[i] = mod-mod/i*inv[mod%i]%mod;
    finv[i] = finv[i-1]*inv[i]%mod;
  }
}

ll nCr(int n, int r) {
  return fact[n]*finv[r]%mod*finv[n-r]%mod;
}

*/

struct state{
  int node;
  int coins;

  state(int x, int y) {
    node = x;coins = y;
  }
};

bool operator<(const state &a, const state &b) {
  return true;
}

const ll INF = 1e15;
vector<int> g[60];
int A[60][60], B[60][60], C[60], D[60], N, M, S;
vector<vector<ll>> d(60, vector<ll>(3000, INF));

void dijkstra(state s) {

    s.coins = min(s.coins, 2500);
    d[s.node][s.coins] = 0;
    set<pair<ll, state>> q;
    q.insert({0, s});
    while (!q.empty()) {
        state v = q.begin()->second;
        q.erase(q.begin());

        for (int to : g[v.node]) {
          if(v.coins < A[v.node][to]) continue;
          state to_state(to, v.coins-A[v.node][to]);
            if (d[v.node][v.coins] + B[v.node][to] < d[to_state.node][to_state.coins]) {
                q.erase({d[to_state.node][to_state.coins], to_state});
                d[to_state.node][to_state.coins] = d[v.node][v.coins] + B[v.node][to];
                q.insert({d[to_state.node][to_state.coins], to_state});
            }
        }

        state to_state(v.node, v.coins+C[v.node]);
        to_state.coins  = min(to_state.coins, 2500);
        if (d[v.node][v.coins] + D[v.node] < d[to_state.node][to_state.coins]) {
            q.erase({d[to_state.node][to_state.coins], to_state});
            d[to_state.node][to_state.coins] = d[v.node][v.coins] + D[v.node];
            q.insert({d[to_state.node][to_state.coins], to_state});
        }

    }
}


int main() {

  //freopen("input.in","r",stdin);
 // freopen("output.out","w",stdout);

  cin >> N >> M >> S;
  rep(i, M) {
    int u,v,a,b;cin>>u>>v>>a>>b;
    u--;v--;
    g[u].pb(v);
    g[v].pb(u);
    A[u][v] = A[v][u] = a;
    B[u][v] = B[v][u] = b;
  }
  rep(i, N) {
    cin >> C[i] >> D[i];
  }
  dijkstra(state(0, S));

  // for(auto row : d) {
  //   ll minm = INF;
  //   for(auto val: row) {
  //     minm = min(val, minm);
  //   }
  //   debug(minm);
  // }
  repi(i, 1, N) {
    ll minm = INF;
    for(auto val: d[i]) {
        minm = min(val, minm);
      }
      cout << minm << endl;
  }


  return 0;
}


Measured memory_bytes: 9412