#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
 
using namespace std;
typedef long long int ll;

class neighbor {
public:
  int ni;  //都市番号
  ll fee;  //移動コスト
  ll time; //移動時間
};
class city {
public:
  vector<neighbor> nb;  //隣接する都市のリスト
  map<ll, ll> state;    //[時刻、所持金]のリスト(同時刻に複数の所持金の状態はない。∵同時刻なら最大の所持金の場合のみ意味があるから
  ll exrate; ll extime;  //換金率、換金時間
};
/*
class state {
public:
  int pos; ll money;
  bool operator <(const state& s) const {
    if (pos < s.pos) return true;
    if (pos == s.pos)
      if (money < s.money) return true;
    else return false;
  }
};
  */
class act {
public:
  ll time;  //現在時刻
  int type; //0:移動, 1:換金
  int from; //移動元/換金場所
  int to;   //移動先
  ll dur;   //移動時間
  ll cost;  //移動コスト
};

int N,M;
ll S;
ll maxcost;

vector<city> ct;
vector<ll> A,B,U,V;
//multimap<state, ll> st;
queue<act> act_q;

void execute_act(act);

int main()
{
  int i,j,k;
  act action;
  neighbor nx;
//  state sx,sy;

  cin >> N >> M >> S;

  ct.resize(N+1);
  U.resize(M+1); V.resize(M+1);
  A.resize(M+1); B.resize(M+1);
  maxcost = 0;
  for (i=1; i<=M; i++) {
    cin >> U[i] >> V[i] >> A[i] >> B[i];
    maxcost += A[i];
  }
  for (i=1; i<=N; i++) {
    cin >> ct[i].exrate >> ct[i].extime;
  }
  for (i=1; i<=M; i++) {
    nx.ni = V[i];
    nx.fee = A[i];
    nx.time = B[i];
    ct[U[i]].nb.push_back(nx);
    nx.ni = U[i];
    ct[V[i]].nb.push_back(nx);
  }
/*
  for (i=1; i<=N; i++) {
    printf("%d: ", i);
    for (j=0; j<ct[i].nb.size(); j++) {
      printf(" %d/%lld/%lld", ct[i].nb[j].ni, ct[i].nb[j].fee, ct[i].nb[j].time);
    }
    printf(" %lld %lld\n", ct[i].exrate, ct[i].extime);
  }
*/
  ct[1].state.emplace(0, S);
  action.time = 0;
  action.type = 0;
  action.from = 1;
  for (neighbor nx:ct[1].nb) {
    action.to = nx.ni;
    action.cost = nx.fee;
    action.dur = nx.time;
    act_q.push(action);
  }
  action.type = 1;
  act_q.push(action);
  while (act_q.size()>0) {
    action = act_q.front();
    act_q.pop();
    execute_act(action);
  }

  for (i=2; i<=N; i++) {
    auto it = ct[i].state.begin();
    printf("%lld\n", it->first);
  }

//  sx.pos = 1;
//  sx.money = S;
//  st.emplace(sx, 0);

//  printf("%lld\n", sum);

  return 0;
}
void execute_act(act a) {
  ll ns, nt, nm;
  act action;
  switch(a.type) {
  case 0: //移動
    ns=ct[a.from].state[a.time]-a.cost;
    if (ns<0) return;  //移動するのに銀貨が足りない
    nt=a.time+a.dur;
    for (auto it = ct[a.to].state.begin(); it != ct[a.to].state.end();) {
      if (it->first <= nt && it->second >= ns) return;  // 移動先に早く（または同じ時間で）到着して、所持金が多く行ける方法がすでにあるのなら、この移動は無意味
      if (it->first >= nt && it->second <= ns) {  //この移動以上に時間かかり、所持金が少ないものは削除対象
        it = ct[a.to].state.erase(it);
      } else {
        it++;
      }
    }
    if (ct[a.to].state.find(nt) != ct[a.to].state.end()) {
      ct[a.to].state.erase(nt);
    }
    ct[a.to].state.emplace(nt, ns);
//printf("move:(時刻:%lld) 都市%d -> 都市%d (所要時間:%lld 費用:%lld 時刻:%lld 残り銀貨:%lld)\n", a.time, a.from, a.to, a.dur, a.cost, nt, ns);
    break;
  case 1: //換金
    if (ct[a.from].state[a.time] > maxcost) return;  //最大コストより多く所持金を増やすのは無意味
    map<ll, ll> nx=ct[a.from].state;
    nm = nx[a.time] + ct[a.from].exrate;
    nt = a.time + ct[a.from].extime;
    for (auto it = ct[a.from].state.begin(); it != ct[a.from].state.end();) {
      if (it->first <= nt && it->second >= nm) return;  // 移動先に早く（または同じ時間で）到着して、所持金が多く行ける方法がすでにあるのなら、この移動は無意味
      if (it->first >= nt && it->second <= nm) {  //この移動以上に時間かかり、所持金が少ないものは削除対象
        it = ct[a.from].state.erase(it);
      } else {
        it++;
      }
    }
//printf("exch:(時刻:%lld) 都市%d 残り銀貨:%lld->%lld 所要時間:%lld 時刻:%lld)\n", a.time, a.from, nx[a.time], nm, ct[a.from].extime, nt);
    ct[a.from].state.erase(nt);
    ct[a.from].state.emplace(nt, nm);
    a.to = a.from;
    break;
  }
  action.time = nt;
  action.type = 0;
  action.from = a.to;
  for (neighbor nx:ct[a.to].nb) {
    action.to = nx.ni;
    action.cost = nx.fee;
    action.dur = nx.time;
    act_q.push(action);
  }
  action.type = 1;
  act_q.push(action);
}
