#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
#define vall(x) (x).begin(), (x).end()
using namespace std;
using lli = long long int;
void YESNO(bool), YesNo(bool);
template <class T1, class T2>
bool chmin(T1 &l, const T2 &r);
template <class T1, class T2>
bool chmax(T1 &l, const T2 &r);
template <class T1, class T2>
void vadd(vector<T1> &v, T2 x);

struct dijkstra
{
  using lli = long long int;
  vector<vector<pair<lli, lli>>> e;
  int n;
  lli inf = 1e18;
  dijkstra(int n) : n(n)
  {
    e.resize(n);
  }
  void add(int a, int b, lli c)
  {
    e[a].push_back(make_pair(b, c));
  }
  void biadd(int a, int b, lli c)
  {
    add(a, b, c);
    add(b, a, c);
  }
  vector<lli> get(int s)
  {
    vector<lli> dist(n, inf);
    dist[s] = 0;
    using p = pair<lli, lli>;
    priority_queue<p, vector<p>, greater<p>> que;
    que.push(make_pair(0, s));
    while (!que.empty())
    {
      lli d = que.top().first;
      lli cur = que.top().second;
      que.pop();
      if (dist[cur] < d)
        continue;
      dist[cur] = d;
      for (auto s : e[cur])
      {
        lli wei = s.second;
        lli to = s.first;
        if (dist[to] > dist[cur] + wei)
        {
          dist[to] = dist[cur] + wei;
          que.push(make_pair(dist[cur] + wei, to));
        }
      }
    }
    return dist;
  }
};
lli get(int i, int j)
{
  return i * 3000 + j;
}
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)
{
  dijkstra dij(N * 3000);
  rep(i, M)
  {
    rep(j, 3000)
    {
      if (j >= A[i])
      {
        dij.add(get(U[i], j), get(V[i], j - A[i]), B[i]);
        dij.add(get(V[i], j), get(U[i], j - A[i]), B[i]);
      }
    }
  }
  rep(i, N)
  {
    rep(j, 3000)
    {
      if (j + C[i] < 3000)
      {
        dij.add(get(i, j), get(i, j + C[i]), D[i]);
      }
    }
  }
  auto s = dij.get(get(0, min(S, (lli)2999)));
  for (int i = 1; i < N; i++)
  {
    lli ret = 1e18;
    rep(j, 3000)
    {
      chmin(ret, s[get(i, j)]);
    }
    cout << ret << endl;
  }
}

signed main()
{
  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]);
    U[i]--;
    scanf("%lld", &V[i]);
    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;
}

// -- lib
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }

template <class T1, class T2>
bool chmin(T1 &l, const T2 &r)
{
  return (l > r) ? (l = r, true) : false;
}

template <class T1, class T2>
bool chmax(T1 &l, const T2 &r)
{
  return (l < r) ? (l = r, true) : false;
}

template <class T1, class T2>
void vadd(vector<T1> &v, T2 x)
{
  for (auto &s : v)
    s += T2(x);
}


Measured memory_bytes: 27456