#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

// verified : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A
// 負辺があると動作しない?
// O(E log V)
template<typename T>
vector<T> dijkstra(vector<vector<pair<int, T>>> &g, int s){
     
  int n = g.size();
  // numeric_limits がうまく使えない場合は自分で INF を定義する.
  const auto inf = numeric_limits<T>::max();
  vector<T> dist(n, inf);

  using P = pair<T, int>;
  // 小さい順に取り出せる
  priority_queue<P, vector<P>, greater<P>> que;
  dist[s] = 0;
  que.emplace(dist[s], s);
  while(!que.empty()){
    T cost;
    int node;
    tie(cost, node) = que.top();
    que.pop();
    if(dist[node] < cost) continue;
    for(auto &e : g[node]){
      auto next_cost = cost + e.second;
      int next_node = e.first;
      if(dist[next_node] <= next_cost) continue;
      dist[next_node] = next_cost;
      que.emplace(next_cost, next_node);
    }
  }

  return dist;
}

struct info {
  int a, b;
  info(int a, int b):a(a),b(b){}
  info(){}
};

int main() {
  
  const lint maxGold = 6000;
  lint toNode[51][6001];
  lint n, m, s; cin >> n >> m >> s;
  s = min(s, maxGold);

  int node = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= maxGold; j++) {
      toNode[i][j] = node;
      node++;
    }
  }
  
  vector<vector<pair<int, info>>> g(n);
  for (int i = 0; i < m; i++) {
    lint u, v, a, b; cin >> u >> v >> a >> b;
    u--;
    v--;
    g[u].push_back({v, info(a, b)});
    g[v].push_back({u, info(a, b)});
  }

  vector<lint> c(n);
  vector<lint> d(n);

  for (int i = 0; i < n; i++) {
    cin >> c[i] >> d[i];
  }

  vector<vector<pair<int, lint>>> gg(node);
  lint S = toNode[0][s];

  // 頂点から頂点へ
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < maxGold; j++) {
      int cur = toNode[i][j];
      lint nxtG = j + c[i];
      nxtG = min(nxtG, maxGold);
      int nxt = toNode[i][nxtG];
      lint cost = d[i];
      gg[cur].push_back({nxt, cost});
    }
  }

  for (int u = 0; u < n; u++) {
    for (int j = 0; j <= maxGold; j++) {
      for (auto e : g[u]) {
        int v = e.first;
        lint a = e.second.a;
        lint b = e.second.b;

        int cur = toNode[u][j];
        if (j < a) continue;
        int nxt = toNode[v][j - a];
        lint cost = b;
        gg[cur].push_back({nxt, cost});
      }
    }
  }

  auto dist = dijkstra(gg, S);

  for (int to = 1; to < n; to++) {
    lint ans = INF;
    for (int j = 0; j <= maxGold; j++) {
      int cur = toNode[to][j];
      ans = min(ans, dist[cur]);
    }
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 54024