import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;
import std.exception;

final class Heap(T) {
  private:
    T [] a;
    int [] h;
    int [] g;
    int n;
    int size;
  pure nothrow @nogc
  void heapifyFront (int k) {
    immutable he = h[k];
    int i = k;
    int j = i << 1;
    while (j <= size) {
      if (j < size && a[h[j+1]] < a[h[j]]) {
        j++;
      }
      if (a[h[j]] >= a[he]) {
        break;
      }
      h[i] = h[j];
      g[h[i]] = i;
      i = j;
      j = i << 1;
    }
    if (i != k) {
      h[i] = he;
      g[he] = i;
    }
  }
  pure nothrow @nogc
  void heapifyBack (int k) {
    immutable he = h[k];
    int i = k;
    while (i > 1) {
      int j = i >> 1;
      if (a[he] >= a[h[j]]) {
        break;
      }
      h[i] = h[j];
      g[h[i]] = i;
      i = j;
    }
    if (i != k) {
      h[i] = he;
      g[he] = i;
    }
  }
  pure nothrow @nogc
  void insert (int i) {
    h[++size] = i;
    g[i] = size;
    heapifyBack (size);
  }
  public:
  pure nothrow @nogc
  void decreaseKey (int k, T value) in {
    assert (k >= 0 && k < n);
    assert (value < a[k]);
  } body {
    a[k] = value;
    immutable pos = g[k];
    if (!pos) {
      insert (k);
    } else {
      heapifyBack (pos);
    }
  }
  pure nothrow @nogc
  void update (int k, T value) in {
    assert (k >= 0 && k < n);
  } body {
    immutable pos = g[k];
    if (!pos) {
      a[k] = value;
      insert (k);
    } else if (value < a[k]) {
      a[k] = value;
      heapifyBack (pos);
    } else if (value > a[k]) {
      a[k] = value;
      heapifyFront (pos);
    }
  }
  pure nothrow @nogc
  int extractMin () {
    assert (size > 0);
    immutable he = h[1];
    g[he] = 0;
    if (--size) {
      h[1] = h[size+1];
      g[h[1]] = 1;
      heapifyFront (1);
    }
    return he;
  }
  pure nothrow @nogc
  inout(T) opIndex (size_t index) inout {
    return a[index];
  }

  @property pure nothrow @nogc
  bool empty () const { return size == 0; }

  this (int n_, T default_value = T.init) {
    n = n_;
    size = 0;
    a = uninitializedArray! (T[]) (n);
    a[] = default_value;
    h = new int[n+1];
    g = new int[n];
  }
}

struct Edge {
  int v;
  int cost, time;
}

void main() {
  int n, m, s;
  readf (" %d %d %d", n, m, s);
  auto e = new Edge[][n];
  foreach (eid; 0 .. m) {
    int u, v, a, b;
    readf (" %d %d %d %d", u, v, a, b);
    --u; --v;
    e[u] ~= Edge (v, a, b);
    e[v] ~= Edge (u, a, b);
  }
  auto c = new int[n];//silver coins incr
  auto d = new int[n];//delay
  foreach (i; 0 .. n) readf (" %d %d", c[i], d[i]);

  auto _max_spent = new int[n];
  _max_spent[] = (n - 1) * 50;
  /*
  foreach_reverse (i; 0 .. n) {
    foreach (const ref q; e[i]) {
      _max_spent[i] = max (_max_spent[i], q.cost + _max_spent[q.v]);
    }
  }
  */
  _max_spent[] += 1;
  auto max_spent = assumeUnique (_max_spent);
  debug stderr.writeln ("max_spent = ", max_spent);
  auto cum_max_spent = max_spent.cumulativeFold!"a+b".array;
  debug stderr.writeln ("cum_max_spent = ", cum_max_spent);
  //[0 .. max_spent[0] + 1]
  auto ss = assumeSorted (cum_max_spent);
  const int nodes = cum_max_spent.back;
  int pack (int k, long coins) {
    int c = (coins > int.max) ? int.max : coins.to!int;
    int res = min (max_spent[k] - 1, c);
    debug stderr.writeln ("res = ", res);
    if (k > 0) res += cum_max_spent[k-1];
    debug stderr.writefln ("pack %d %d -> %d", k, coins, res);
    return res;
  }
  void unpack (in int node, out int v, out int coins) {
    v = ss.lowerBound (node+1).length.to!int;
    coins = node;
    if (v > 0) {
      coins -= cum_max_spent[v-1];
    }
    debug {
      //stderr.writefln!"unpack %d %d %d"(node, v, coins);
      assert (pack (v, coins) == node);
    }
  }
  const long inf = long.max / 2;
  auto heap = new Heap!long (nodes, inf);
  int start = pack (0, s);
  heap.decreaseKey (start, 0);
  while (!heap.empty) {
    const int x = heap.extractMin ();
    debug stderr.writefln!"x = %d"(x);
    int i, coins;
    const int ms = max_spent[i];
    unpack (x, i, coins);
    long t = heap[x];
    debug stderr.writefln!"i = %d, coins = %d, t = %d"(i, coins, t);
    int u = coins;
    while (true) { 
      t += d[i];
      u += c[i];
      const int j = pack (i, u); 
      if (heap[j] > t) heap.decreaseKey (j, t);
      if (u >= ms) {
        break;
      }
    }
    foreach (const ref q; e[i]) if (coins >= q.cost) {
      t = heap[x] + q.time;
      u = coins - q.cost;
      const int j = pack (q.v, u); 
      if (heap[j] > t) heap.decreaseKey (j, t);
    }
  }
  auto dist = new long[n];
  dist[] = inf;
  dist[0] = 0;
  foreach (x; 0 .. nodes) {
    int i, coins;
    unpack (x, i, coins);
    if (dist[i] > heap[x]) dist[i] = heap[x];
  }
  writefln!"%(%s\n%)"(dropOne(dist));
}



Measured memory_bytes: 5016