#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i32 = int32_t;
using i64 = int64_t;
constexpr char newl = '\n';

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = (b-1); i >= a; i--)
#define RF0(i,b) RFO(i,0,b)
#define F first
#define S second
#define debug(x) cout << #x << ": " << x << '\n';


// 再帰呼び出ししたいラムダ式を書くときに使う
// MFP([&](auto dfs, int v, int p)->int {
//   // ここで dfs(a, b) の呼び出しが可能
// })(0, -1);
template<typename F>
struct FixPoint : F {
  FixPoint(F&& f) :F(forward<F>(f)) {}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F && f) {
  return FixPoint<F>{forward<F>(f)};
}


struct Link {
  int dest;
  int cost;
  i64 time;
  Link(int dest, int cost, i64 time) {
    this->dest = dest;
    this->cost = cost;
    this->time = time;
  }
};

struct City {
  vector<Link> links;
  i64 cost, time;
  i64 best = INT64_MAX;
  int id;
  string ToString() {
    return "C#" + to_string(id);
  }
};

struct Travel {
  int silver; // 路銀
  i64 time = 0; // 掛かった時間
  set<City*> visits;  // 行ったCity
  // 前回このcityに来たときのvisitsの数を記憶。
  // これが増えないような移動はしないようにする
  unordered_map<City*, int> memory;

  Travel(int silver) {
    this->silver = silver;
  }
  Travel(Travel &t, int silver, int time) {
    this->visits = t.visits;
    this->memory = t.memory;
    this->silver = silver;
    this->time = time;
  }

  void Print() {
    cout << "Travel" << newl;
    cout << "  silver=" << silver << " time=" << time << newl;
    cout << "  visits=";
    for (auto c : visits) {
      cout << c->ToString() << " ";
    }
    cout << newl;
    cout << "  memory=";
    for (auto pair : memory) {
      cout << pair.first->ToString() << "=" << pair.second << " ";
    }
    cout << newl;

  }
};

constexpr int State(u8 city, u16 silver) {
  return (((i32)city) << 16) | silver;
}
constexpr u8 StateCity(int state) {
  return (u8)(state >> 16);
}
constexpr u16 StateSilver(int state) {
  return (u16)(state & 0xffff);
}

// INSERT ABOVE HERE
#if 1
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, M;
  i64 S;
  cin >> N >> M >> S;

  vector<City> cities(N);
  vector<int> fares(M);
  F0R(i, M) {
    int u, v, a;
    i64 b;
    cin >> u >> v >> a >> b;
    u--; v--;
    cities[u].links.emplace_back(v, a, b);
    cities[v].links.emplace_back(u, a, b);
    fares[i] = a;
  }
  F0R(i, N) {
    cin >> cities[i].cost >> cities[i].time;
    // debug
    cities[i].id = i;
  }

  // 運賃を高い方から順に N-1 個足し合わせた数が、最大交通費
  int fareSum = 0;
  sort(fares.begin(), fares.end(), greater<int>());
  F0R(i, N - 1) {
    fareSum += fares[i];
  }

#if 0

  auto states = vector<vector<i64>>(N, vector<i64>(fareSum, INT64_MAX));

  struct State {
    int city;
    int silver;
    i64 time = INT64_MAX;
    State(int city, int silver) :
      city(city), silver(silver)
    {
    }
  };

  auto compare = [&states](const pair<int, int>& a, const pair<int, int>& b) {
    return states[a.first][a.second] > states[b.first][b.second];
  };

  // コンテナは vector か deque
  priority_queue<pair<int,int>, vector<pair<int, int>>, decltype(compare)> cqueue{ compare };
  cqueue.emplace(0, S);
#endif

  // priority_queueだと
  // Dijkstra 法の中で要素ごとの最短距離（優先度）が変化していくのに対応できない
  
  struct State {
    u8 city;
    u16 silver;
    i64 time;
    State(u8 city, u16 silver, i64 time) :
      city(city), silver(silver), time(time)
    {

    }
  };

  // unordered_map は std::sort できない
  // key ではなく value で並び変えたいので map も違う。
  // 全要素探索するしかない？

  auto times = vector<vector<i64>>(N, vector<i64>(fareSum + 1, INT64_MAX));

  auto comp = [&times](const pair<int, int>& a, const pair<int, int>& b) {
    return times[a.first][a.second] > times[b.first][b.second];
  };
  auto comp2 = [](const State& a, const State& b) {
    return a.time > b.time;
  };
  auto pq = priority_queue<State, vector<State>, decltype(comp2)>({ comp2 });

  chmin(S, fareSum);

  // initial state
  times[0][S] = 0;
  pq.emplace(0, S, 0);

  // dijkstra's algorithm
  while (pq.size() > 0) {
    // 最小のものを取り出す
    auto p = pq.top();
    pq.pop();
    i64 m = times[p.city][p.silver];
    if (m < p.time) {
      continue;
    }
    u8 sc = p.city;
    u16 ss = p.silver;
    auto &city = cities[sc];
    //debug((int)sc);
    //debug(ss);

    if (city.best == INT64_MAX) {
      city.best = m;
    }

    // 全ての移動
    for (auto &link : city.links) {
      if (ss >= link.cost) {
        i64 time = m + link.time;
        u16 ns = ss - link.cost;
        if (times[link.dest][ns] > time) {
          times[link.dest][ns] = time;
          pq.emplace(link.dest, ns, time);
        }
      }
    }

    // 換金
    i64 time = m;
    if (ss < fareSum) {
      ss += city.cost;
      chmin(ss, fareSum);
      i64 time = m + city.time;
      if (times[sc][ss] > time) {
        times[sc][ss] = time;
        //cout << (int)sc << "," << ss << "=" << time << newl;
        pq.emplace(sc, ss, time);
      }
    }
  }

  FOR(i, 1, N) {
    //sort(times[i].begin(), times[i].end(), less<i64>());
    //cout << *times[i].begin() << newl;
    cout << cities[i].best << newl;
  }
}
#endif


Measured memory_bytes: 5044