#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;

struct Edge {
  int to, cost, money;
  Edge(){}
  Edge(int to, int cost, int money) : to(to), cost(cost), money(money) {}
  bool operator < (const Edge &r) const {
    return cost < r.cost;
  }
};

signed main() {
  int N, M, S;
  cin >> N >> M >> S;

  int MAX = N*50;
  S = min(MAX, S);
  vector<vector<Edge>> graph(N);
  vector<int> u(M), v(M), a(M), b(M);
  REP(i, M){
    cin >> u[i] >> v[i] >> a[i] >> b[i];
    u[i]--; v[i]--;

    graph[u[i]].emplace_back(v[i], b[i], a[i]);
    graph[v[i]].emplace_back(u[i], b[i], a[i]);
  }

  vector<int> c(N), d(N);
  REP(i, N) cin >> c[i] >> d[i];

  vector<vector<int>> dist(N, vector<int>(MAX+5, INF));
  dist[0][S] = 0;

  queue<pair<int, int>> q;
  q.push({0, S});

  while(!q.empty()){
    auto p = q.front(); q.pop();
    int v = p.first;
    int m = p.second;

    if(m+c[v] <= MAX){
      if(dist[v][m+c[v]] > dist[v][m]+d[v]){
        dist[v][m+c[v]] = dist[v][m]+d[v];
        q.push({v, m+c[v]});
      }
    }
    for(auto u : graph[v]){
      if(m-u.money >= 0 && dist[u.to][m-u.money] > dist[v][m]+u.cost){
        dist[u.to][m-u.money] = dist[v][m]+u.cost;
        q.push({u.to, m-u.money});
      }
    }
  }

  FOR(i, 1, N){
    int ret = INF;
    REP(j, MAX){
      chmin(ret, dist[i][j]);
    }

    cout << ret << "\n";
  }

  return 0;
}