#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
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; }
typedef long long ll;
template <typename X = int>
struct Edge{
  int from;
  int to;
  X cost;
  int charge;
  
  Edge() = default;

  Edge(int from, int to, X cost, int charge) : from(from), to(to), cost(cost), charge(charge) {}
};

template <typename X>
struct Node{ // priority_queueに入れる頂点の情報
  int idx;
  int coin;
  X dis;
  
  Node() = default;

  Node(int idx, int coin, X dis) : idx(idx), coin(coin), dis(dis) {}
  
  bool operator == (const Node& r) const {
    return (idx == r.idx && dis == r.dis && coin == r.coin); 
  }

  bool operator != (const Node& r) const {
    return !(*this == r);
  }

  bool operator < (const Node& r) const {
    return dis > r.dis;
  }

  bool operator > (const Node& r) const {
    return dis < r.dis;
  }  
};

template <typename X = int>
struct Vertex{
  int rate;
  X time;

  Vertex() = default;

  Vertex(int rate, X time) : rate(rate), time(time) {}

};

template <typename X = int>
class Graph{
private:
  int n;
  int m;
  vector<vector<Edge<X>>> edge;
  vector<vector<vector<X>>> d;
  vector<Vertex<X>> vertex;
  
  const X inf = 1e+17;
  int M = 2500;

public:
  Graph(int n) : n(n) {
    edge.resize(n);
  }

  Graph(int n, int m, vector<int> a, vector<int> b, vector<X> c, vector<int> e) : n(n), m(m){
    edge.resize(n);
    rep(i,m) {
      add_edge(a[i], b[i], c[i], e[i]);
      add_edge(b[i], a[i], c[i], e[i]);
    }
  }

  void add_edge(int from, int to, X cost, int charge) {
    edge[from].emplace_back(from, to, cost, charge);
  }

  void Init_Vertex(vector<int> _rate, vector<X> _time) {
    rep(i,n) {
      vertex.emplace_back(_rate[i], _time[i]);
    }
  }
  
  void dijkstra(int s, int g) {
    d.resize(n);
    d[s].resize(n ,vector<X>(M+1, inf));
    chmin(g, M);
    d[s][s][g] = 0;
    priority_queue<Node<X>> pq;
    pq.emplace(s, g, 0);
    while( !pq.empty() ) {
      Node<X> p = pq.top(); pq.pop();
      int v = p.idx; // 頂点
      X dist = p.dis; // s->vの最短距離
      if(p.coin < M) {
	if(chmin(d[s][v][min(M, p.coin + vertex[v].rate)], d[s][v][p.coin] + vertex[v].time)) {
	  pq.emplace(v, min(M, p.coin + vertex[v].rate), d[s][v][min(M, p.coin + vertex[v].rate)]);
	}
      }
      if(d[s][v][p.coin] < dist) continue;
      for(auto w: edge[v]) {
	if(p.coin < w.charge) continue;
	if(chmin(d[s][w.to][p.coin - w.charge], d[s][v][p.coin] + w.cost)) {
	  pq.emplace(w.to, p.coin - w.charge, d[s][w.to][p.coin - w.charge]);
	}
      }
    }
  }

  X get_d(int u, int v, int w) { return d[u][v][w]; }
  X get_inf() { return inf; }
  
};

int main()
{
  int n,m,s; cin >> n >> m >> s;
  vector<int> u(m), v(m), a(m), c(n);
  vector<ll> b(m), d(n);
  rep(i,m) {
    cin >> u[i] >> v[i] >> a[i] >> b[i];
    u[i]--; v[i]--;
  }
  rep(i,n) cin >> c[i] >> d[i];
  
  Graph<ll> gp(n, m, u, v, b, a);
  gp.Init_Vertex(c, d);
  gp.dijkstra(0, s);

  rep1(i,n-1) {
    ll res = 1e+17;
    rep(j,2501) {
      chmin(res, gp.get_d(0, i, j));
    }
    cout << res << "\n";
  }
  
  return 0;
}


Measured memory_bytes: 6224