/*
    特徴
          */
// ダイクストラ
// グラフの頂点を倍加
// ゲームの局面をグラフの頂点、指し手を頂点間の移動としてとらえる

/*
    教訓
          */
// 全体を俯瞰するのではなく、「局面」に意味のある違いがあるかを考える

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld  = long double;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-9; //微調整用（EPSより小さいと0と判定など）

//MODINT
//変数名.nでint型の数値を受け取る
struct mint {
  int n;
  mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

int ii() { int x; scanf("%d", &x); return x; }
long long il() { long long x; scanf("%lld", &x); return x; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
// long doubleで受け取り、fをLfなどに変えて出力すると、変な数値が出る
// それをなんとかするには独自の出力を作らなければならなそう
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
//GCC9.2.1に変わって動かなくなったので一旦消した そのうち原因を調べる
//auto op = [&](auto p) -> void{ cout << p; };
//auto ov = [&](auto vec) -> void{ cout << vec; };
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認
void br() { putchar('\n'); }

#define gcd __gcd //llは受け取ってくれない
int lcm(int a, int b){return a / gcd(a, b) * b;}
#define ALL(a) a.begin(),a.end() //sort(ALL(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll) (n) ; i++ )
#define rep(i,n) REP(i,0,n)
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define PB push_back
#define SZ(x) ((int)(x).size) //size()がunsignedなのでエラー避けに

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// 空白区切りだけ --> return s << "(" << p.first << " " << p.second << ")";
// 見やすくしたいとき --> return s << "(" << p.first << " " << p.second << ")";
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値を更新する。aよりbのが大きい（小さい）か等しければaを更新してtrueを返す。そうでなければ何もせずfalseを返す chmax(nowmax,x);
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

// -------- template end - //


// - global -------------- //



// ---------- global end - //


// - library ------------- //

//Dijkstra（今のところ経路復元はできない）
//vector<Weight>の形式で、sから全頂点への最短経路における総weightを返す。
//戻り値.at(t)でtへの最短経路の総weightになる

//Dijkstraのベースになるデータ構造を宣言
// !! 重み（コスト）の型をここで設定する !!
using Weight = ll; //<---ここ！！
const Weight INFW = numeric_limits<Weight>::max();

struct Edge{
    int from, to;
    Weight wei;
    // struct Edge のコンストラクタ
    Edge(int from_, int to_, Weight wei_):from(from_),to(to_),wei(wei_){}
};
// struct Edge のvectorをEdgesとする
typedef vector<Edge> Edges;

// グラフ全体の構造体を定義
// 実態は、各頂点に張られた辺たち（Edges）の集合体（Edgesのvector）
// Graph[v] は vector<頂点vに張られた辺>
struct Graph : public vector<Edges>{
  //struct Graphのコンストラクタ 引数Vを与える
    Graph(){ }
    Graph(int V): vector<Edges>(V){ }
    /*
    有向辺を追加する
    */
    void addEdge(int from, int to, Weight wei=1){
      // Graph[from頂点] （from頂点から張られたEdges）に新しい辺を追加する
      // 辺に重みの差が無い（全て1とみなせる）場合、重みを引数として渡さなくても1とみなして処理
        (*this)[from].PB(Edge(from, to, wei));
    }
    /*
    無向辺を追加する
    */
    void addUEdge(int u, int v, Weight wei=1){
      (*this)[u].PB(Edge(u, v, wei));
      (*this)[v].PB(Edge(v, u, wei));
    }
};
 
//ここから実際に使う関数

// Edge > Edge の比較は、重みの大小で評価
bool operator>(const Edge &a, const Edge &b){
    return a.wei>b.wei;
}

//戻り値のvector<Weight>にvec.at(頂点のidx)をすれば、各頂点に到達するまでに最低限必要な重みの合計（以降、累計重みと呼ぶ）が得られる
//dijkstra(Graph, スタート地点のidx) で呼び出す
// const は「関数内でGraphを変更しません」という意味で、&は単にコピーの時間を省くためと思われる
vector<Weight> dijkstra(const Graph &G, int src){

  // 型 p_wei_vert : pair<Weight, int> を定義
  // pair<その頂点に辿り着くまでの最小累計重み（最短経路の重み）, 頂点番号>
    typedef pair<Weight, int> p_wei_vert;
    // 最小値を取り出すpriority_q : 「これから訪れたい頂点と、その頂点までの累計重み」を入れる
    // vector <p_wei_vert<累計重み, 行き先頂点> >
    priority_queue<p_wei_vert, vector<p_wei_vert>, greater<p_wei_vert>> pq_to_visit;
    // pair {累計重み0, スタート地点のidx}の追加
    pq_to_visit.push(MP(0, src));
    // 頂点数を受け取っただけ
    int V = (int)G.size();

    vector<Weight> res(V, -1);
    // res はDP[]のようなもので、res[v] : vに辿り着く最小累計重み
    // res[v] == -1であれば、未到達
    // res[v] != -1であれば頂点vに到達済みで、到達済みであれば、イコール最短経路確定済となる（理由は後で）
    // ちなみにダイクストラを使う場合、重みは正（非負？）のはずだから、既に到達した頂点のres値が負となることはない

    while(pq_to_visit.size()){
      // pqから、重み最小のp_wei_vert（cost, vert）を取り出してp_wei_vert pに入れる
      // つまり、「今行ける場所の中で、最も累計重みの低い場所に行こうとしてみる」ということ
        auto p = pq_to_visit.top(); pq_to_visit.pop();
        Weight d = p.first;
        int v = p.second;
        if(res[v] > -0.5)continue;
        // res[v]が非負、つまり頂点vに過去に到達済みなら、pq_to_visitに追加せず次のループへ
        // ループを抜けたなら過去に到達していないので、今回のルートが「頂点vへの最短経路」
        // これでres[v] つまりvへの最短経路での重み は確定であり、再度代入することはない
        res[v] = d;

        // Graph[v] すなわちvに張られた全てのEdgeについてループし、vから移動できる頂点を探す
        for(const auto &edge : G[v]){
            int to = edge.to;
            Weight wei = edge.wei;
            
            if (res[to] > -0.5) continue; 
            // 枝刈り（既に探索済み = 頂点toの累計最小重みが確定しれば、pqに入れない）
              
            pq_to_visit.push(MP(d + wei, to));
            // pqに、今見ている頂点vから移動できる、まだ訪問していない頂点の情報を入れる
            // 入れるのは「頂点vの到達までの累計重み（d = p.first） + wei（pから張られた辺の重み）, 行き先」
            // while 文の最初の方で累計重みが小さい方から取り出して訪問するために使う。その際「まだ訪問していない頂点のうち、スタートから最も小さい重みで行ける頂点」を訪問していくことにより、その訪問の仕方が、その頂点まで最も小さい重みで行ける経路であることが担保される（ダイクストラのアルゴリズム）
        }
    }
    // 最終的に、resは「各頂点に辿り着くための最小重み」となっているので、それを返す
    return res;
}

// 都市の番号, 所持金　を 倍加グラフ上の頂点の添字に変換する
ll uv_to_idx(ll u, ll sil){
  return u * 2501 + sil;
}


// --------- library end - //


// - main() -------------- //

int main(){

  ll N, M, S;
  cin >> N >> M >> S;

  vector<vector<ll> > UVABs;
  vector<pair<ll, ll> > CDs;

  rep(i, M){
    ll u = ii() - 1; // 0-indexedにする
    ll v = ii() - 1;
    ll a = ii();
    ll b = ii();
    // from, to, silcost, wei(かかる時間)
    UVABs.PB({u, v, a, b});
  }

  rep(i, N){
    ll c = ii();
    ll d = ii();
    CDs.PB({c, d});
  }

  /*
   頂点を倍加（次元拡張）したグラフ上でのダイクストラ
  */

  // 今回ダイクストラを動かすグラフの概要

  // 「現在どの都市にいて」「いくつの銀貨を持っているか」のどちらか一つでも違うことを「異なる局面」と捉え、異なる各局面を頂点としたグラフを考える（グラフ倍加）
  // すると、頂点を特定する添字は2つ（都市 u, 所持銀貨 sil）必要だが、 ダイクストラのライブラリを変えると大変なので、
  // 倍加した頂点 の添字 = u * 2501 + sil として考える。

  // なぜか？
  // 都市50個、最高運賃sil50なので、sil2500あれば「現在いる地点からゴールまで両替せずに進み続けられる」という状態になる。すると、「局面としては」sil2500あってもsil2550あっても全く違いはない。そこで、sil2501~はsil2500と同一視する。
  // なお、「一度どこかの都市に寄って効率のよい両替をしてから、前にいた都市に戻って、また先に進む」という行動が最適となる場合も考えられる。そういう場合、「スタートからゴールまで累計で消費したsil」は、2500を超えることはありえる。そうだとしても、「各局面」から考えれば、2500以上のsilをいくら持っていようが関係ない（ある時点で2500を超えれば、あとは両替を一度もせずに行ける）ので、やはり2501以上は考える必要がない。

  // ということで、都市0 sil0~2500, 都市1 sil0~2500 という各局面を表す数字としては、「1桁目が sil で、2501で2桁目の u に繰り上がる 2501進数」と考えればいい。
  // 添字が最大となる頂点は「u = N, sil = 2500」なので、u=0, sil=0も忘れずにカウントして、頂点数はN * 2501 + 2500 + 1
  Graph graph(N * 2501 + 2500 + 1); // 頂点数を入れて宣言しないとバグる


  // 頂点に辺を張っていく

  // 辺が2種類あることに気を付ける
  // 1. 通常の辺。sil が足りている場合に、silを消費して次の都市へ移動する
  // 2. 倍加したことで発生した辺。sil<=2499以下の場合に、時間だけ消費してsilを購入する
  //    なお、2.の場合において、金貨の枚数は無視する（十分大きいので）

  // 通常の辺（1.）を張る
  rep(i, M){
    ll from = UVABs[i][0];
    ll to = UVABs[i][1];
    ll silcost = UVABs[i][2];
    ll timecost = UVABs[i][3];

    // 都市を移動する辺を張るが、お金が足りない場合は移動できない
    // ということで、所持金sil=ピッタリ運賃分(silcost)から始めて、2500までループ
    REP(sil, silcost, 2501){
      graph.addEdge(uv_to_idx(from, sil), uv_to_idx(to, sil-silcost), timecost);
      // 有向辺を張る。お金がある状態から、運賃を引かれた状態への遷移なので、反対の方向である「運賃を引かれた状態から、お金がある状態への遷移」は不可能
      // 引数は 移動元添字, 移動先添字, 所要時間

      // 反対側からの辺を張る。反対側からも、同じ所持金があれば移動できるので、sil, silcostは考え方を変えなくていい
      graph.addEdge(uv_to_idx(to, sil), uv_to_idx(from, sil-silcost), timecost);

    }
  }

  // 次に、銀貨を買う場合の辺（2.）を張る
  // sil==2500ならば買う意味がないので張らないことと、買った後にsil>2450になる場合も2450に切り下げることに注意する
  // なお、都市で両替をするので、ループは都市の数＝N回となる
  rep(i, N){
    ll city = i; // 分かりやすく変数名を変えただけ
    ll silgain = CDs[city].first;
    ll timecost = CDs[city].second;

    // フラグがtrueの間、購入ループを回す（何度も買うという処理はしない（そういう概念はない）。「一回の購入」が頂点（局面）から頂点（局面）への遷移なので、「購入前の所持金」を増やしてループすることで、異なる頂点（所持金が異なる局面）からの辺を処理していることになる。
    // つまり、「各都市での購入」という手順についてのループ（外側のループ）と、「同じ都市での、異なる所持金局面でのループ」という所持金局面でのループ（内側のループ）を回している
    // なお元の所持金が2500以上のときに買い足す選択は最短経路の選択としてあり得ないので、sil=2499までについてループする
    // 2500以上は2500と変わらないので、min(購入後所持金, 2500)を行う
    rep(sil, 2500){
      // これも都市の移動と同様、「金貨を払って銀貨を買う」という遷移はあっても、「銀貨を売って金貨をもらう」という遷移はないので、無向辺となる。
      graph.addEdge(uv_to_idx(city, sil), uv_to_idx(city, min(sil + silgain, 2500LL)), timecost);
    }
  }
  
  // 初期所持金は2500を超えていても何の意味もないので、2500に切り下げる
  // 一瞬、「でも途中で所持金が2500を切るような体になっちゃうからおかしいのでは？」と思うけれども、そのような場合でも関係無い。2500を切って本来と食い違った場合でも、考えられるのは「一度も購入せずに突っ切る」場合と「一度以上購入する」場合で、まず後者は「十分余っているのに購入している」時点で非効率であり、最終的には切り捨てられる経路。また一度も購入せずに突っ切る場合、その経路も最短経路としてダイクストラの答えになるが、それが「より効率のよい経路」を邪魔することは考えられない。何故なら、より効率のよい経路があるなら既に探索されている＝ダイクストラの処理内で、priority_queueに入らず枝刈りされるからである。
  vector<Weight> result = dijkstra(graph, uv_to_idx(0, min(S, 2500LL)));
  
  
  // 都市2~N -> 0-indexedに変換してるので都市1~N-1の最小累計重みを探して出力
  REP(i, 1, N){
    // 都市iは銀貨数によって場合分けされ倍加された頂点になっているので、
    // その倍加された頂点のうち、もっとも重みが軽いものを取り出す
    ll min_totaltime = LINF;
    rep(sil, 2501){
      // 倍加された頂点はsil 0~2500に分けられているので、それらのうち最小値を探す
      // ただし 累計重み -1 となっているのは未到達頂点なのでダメ
      ll now_totaltime = result.at(uv_to_idx(i, sil));
      if (now_totaltime < -0.5) continue;
      chmin(min_totaltime, now_totaltime);
    }
    ol(min_totaltime);
    br();
  }


// ---------- main() end - //
}

Measured memory_bytes: 26044