#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;

// chmax, chmin
template <class T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
function<T(T, T)> op_max = [](T a, T b) -> T { return max(a, b); };
template <typename T>
function<T(T, T)> op_min = [](T a, T b) -> T { return min(a, b); };

template <typename T>
function<T(T, T)> op_sum = [](T a, T b) -> T { return a + b; };

using namespace std;
//********************  dumps ************************//

template <typename T>
void dump(const T &data, vector<int> &iter)
{
  cout << data << " ";
}
template <typename T>
void dump(const vector<T> &data, vector<int> &iter)
{
  for (auto elem : data)
    dump(elem, iter);
  cout << endl;
}

template <typename T>
void dump(const vector<vector<T>> &data, vector<int> &iter)
{
  for (auto elem : iter)
  {
    cout << "[" << elem << "]";
  }
  cout << endl;
  for (int i = 0; i < data.size(); i++)
  {
    iter.push_back(i);
    dump(data[i], iter);
    iter.pop_back();
  }
  cout << endl;
}

template <typename T>
void dump(const vector<T> &data, int dummy)
{
  for (int i = 0; i < data.size(); i++)
  {
    cout << "[" << i << "] " << data[i] << endl;
  }
}
template <typename T>
void dump(const T &data)
{ // T : data, U = base type val.
  vector<int> iter;
  dump(data, iter);
}
///////////////////////////////////////////////

template <typename TE>
class Edge
{
public:
  int to;
  TE field;
  Edge() {}
  Edge(int t, TE f) : to(t), field(f) {}
};

template <typename TV, typename TE>
class Vertex
{
public:
  int id;
  int depth;
  TV field;
  Edge<TE> parent;
  vector<Edge<TE>> child;
  vector<Edge<TE>> es;
  Vertex() {}
  Vertex(int in) : id(in) {}
};

template <typename TV, typename TE>
class Graph
{
public:
  int root;
  int N;
  vector<Vertex<TV, TE>> vs;
  // vector<vector<Edge>> es;
  Graph(int n) : N(n)
  {
    for (int i = 0; i < n; i++)
    {
      vs.push_back(Vertex<TV, TE>(i));
    }
    root = -1;
  }
  // 0-indexed
  void add_edge(int v, int u, TE e, bool directed = false)
  {
    vs[v].es.push_back(Edge<TE>(u, e));
    if (!directed)
    {
      vs[u].es.push_back(Edge<TE>(v, e));
    }
  }

  void build_tree(
      int root, function<void(Vertex<TV, TE> &, Vertex<TV, TE> &)> func =
                    [](Vertex<TV, TE> &parent, Vertex<TV, TE> &child) {
                      if (parent.id == -1)
                      {
                        child.depth = 0;
                        return;
                      }
                      child.depth = parent.depth + 1;
                    })
  {
    Vertex<TV, TE> dummy(-1);
    this->root = root;
    func(dummy, vs[root]);
    vector<int> used(N);
    stack<int> sta;
    sta.push(root);
    used[root] = true;
    while (!sta.empty())
    {
      int v = sta.top();
      sta.pop();
      for (auto e : vs[v].es)
      {
        int u = e.to;
        if (used[u])
          continue;
        used[u] = true;
        vs[u].parent = Edge<TE>(v, e.field);
        vs[v].child.push_back(Edge<TE>(u, e.field));
        func(vs[v], vs[u]);
        sta.push(u);
      }
    }
  }

  vector<LL> dijkstra(int s)
  {
    LL INF = (1LL << 60);
    priority_queue<PII, vector<PII>, greater<PII>> que;
    vector<LL> d(N, INF);
    d[s] = 0;
    que.push(PII(0, s));
    while (!que.empty())
    {
      PII p = que.top();
      que.pop();
      int v = p.second;
      if (d[v] < p.first)
        continue;

      for (auto e : vs[v].es)
      {
        if (d[e.to] > d[v] + e.field)
        {
          d[e.to] = d[v] + e.field;
          que.push(PII(d[e.to], e.to));
        }
      }
    }
    return d;
  }
};
void solve(long long N, long long M, long long S, std::vector<long long> U, std::vector<long long> V, std::vector<long long> A, std::vector<long long> B, std::vector<long long> C, std::vector<long long> D)
{

  int coins = 5010;
  Graph<int, int> G(N * coins);
  auto get_index = [&](int i, int j) {
    return i * coins + j;
  };
  for (int i = 0; i < M; i++)
  {
    int u = U[i];
    int v = V[i];
    u--;
    v--;
    int a = A[i];
    int b = B[i];
    for (int z = 0; z < 2; z++, swap(v, u))
    {
      for (int j = 0; j < coins; j++)
      {
        if (j < a)
          continue;
        G.add_edge(get_index(u, j), get_index(v, j - a), b, true);
      }
    }
  }
  for (int i = 0; i < N; i++)
  {
    int c = C[i];
    int d = D[i];
    for (int j = 0; j < coins; j++)
    {
      if (j + c >= coins)
        continue;
      G.add_edge(get_index(i, j), get_index(i, j + c), d, true);
    }
  }
  auto ds = G.dijkstra(get_index(0, min((int)S, coins - 1)));
  for (int i = 1; i < N; i++)
  {
    LL ans = 1LL << 60;

    for (int j = 0; j < coins; j++)
    {
      chmin(ans, ds[get_index(i, j)]);
    }
    cout << ans << endl;
  }
}

int main()
{
  cout << setprecision(10);
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  long long S;
  scanf("%lld", &S);
  std::vector<long long> U(M);
  std::vector<long long> V(M);
  std::vector<long long> A(M);
  std::vector<long long> B(M);
  for (int i = 0; i < M; i++)
  {
    scanf("%lld", &U[i]);
    scanf("%lld", &V[i]);
    scanf("%lld", &A[i]);
    scanf("%lld", &B[i]);
  }
  std::vector<long long> C(N);
  std::vector<long long> D(N);
  for (int i = 0; i < N; i++)
  {
    scanf("%lld", &C[i]);
    scanf("%lld", &D[i]);
  }
  solve(N, M, S, std::move(U), std::move(V), std::move(A), std::move(B), std::move(C), std::move(D));
  return 0;
}


Measured memory_bytes: 45648