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

//////////////////////////////   Begin Macros

#define all(x) (x).begin(), (x).end()
#define rep(i, N) for (int i = 0; i < (int)(N); i++)
#define reprev(i, N) for (int i = (int)(N)-1; i >= 0; i--)
#define rep1(i, N) for (int i = 1; i <= (int)(N); i++)
#define rep1rev(i, N) for (int i = (int)(N); i >= 0; i--)
#define forbe(i, b, e) for (int i = (b); i < (e); i++)
#define forberev(i, b, e) for (int i = (e)-1; i >= (b); i--)
#define forfl(i, f, l) for (int i = (f); i <= (l); i++)
#define forflrev(i, f, l) for (int i = (l); i >= (f); i--)
using ll = long long int;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

template <typename T>
bool chmax(T &m, const T q)
{
  if (m < q)
  {
    m = q;
    return true;
  }
  else
    return false;
}
template <typename T>
bool chmin(T &m, const T q)
{
  if (m > q)
  {
    m = q;
    return true;
  }
  else
    return false;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return {l.first + r.first, l.second + r.second}; }
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return {l.first - r.first, l.second - r.second}; }
template <typename T>
pair<T, T> operator*(const pair<T, T> &l, const T &r) { return {l.first * r, l.second * r}; }
template <typename T>
pair<T, T> operator/(const pair<T, T> &l, const T &r) { return {l.first / r, l.second / r}; }
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
  for (auto &v : vec)
    is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
  os << "[";
  for (auto v : vec)
    os << v << ",";
  os << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec)
{
  os << "deq[";
  for (auto v : vec)
    os << v << ",";
  os << "]";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &vec)
{
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &vec)
{
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &vec)
{
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &vec)
{
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{
  os << "(" << pa.first << "," << pa.second << ")";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp)
{
  os << "{";
  for (auto v : mp)
    os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp)
{
  os << "{";
  for (auto v : mp)
    os << v.first << "=>" << v.second << ",";
  os << "}";
  return os;
}

template <typename T>
void reset(vector<T> &v, const T reset_to)
{
  for (auto &x : v)
    x = reset_to;
}
inline int popcount(const unsigned int x) { return __builtin_popcount(x); }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

ll nC2(ll n)
{
  return n * (n - 1) / 2;
}

const int intinf = numeric_limits<int>::max();
const ll llinf = numeric_limits<ll>::max();
const pii udlr[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

//////////////////////////////   End Macros

// Graph.h start--------------------------------------------
#pragma once

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

template <typename Weight>
struct Vertex;
template <typename Weight>
struct Edge;

template <typename Weight>
struct Vertex
{
  int id;
  vector<int> ids_dst;
  vector<Edge<Weight>> edges;

  Vertex(const int id = 0) : id(id){};
  int &operator[](int n) { return ids_dst[n]; }
  const int &operator[](int n) const { return ids_dst[n]; }

  size_t size() const { return edges.size(); }
  void add_edge(const Edge<Weight> &);
};

template <typename Weight>
struct Edge
{
  int id_src, id_dst;
  Weight weight;

  Edge(const int id_src, const int id_dst) : id_src(id_src), id_dst(id_dst){};
  Edge(const int id_src, const int id_dst, const Weight weight) : id_src(id_src), id_dst(id_dst), weight(weight){};
};
template <typename Weight>
ostream &operator<<(ostream &os, const Edge<Weight> &e) { return os << "Edge(" << e.id_src << "->" << e.id_dst << "," << e.weight << ")"; }

template <typename Weight = long long>
struct Graph
{
  vector<Vertex<Weight>> vertices;
  vector<Edge<Weight>> edges;

  Graph(const int nvertices = 0);
  Vertex<Weight> &operator[](int n) { return vertices[n]; }
  const Vertex<Weight> &operator[](int n) const { return vertices[n]; }

  size_t size() const { return vertices.size(); }
  void add_edge(const Edge<Weight> &);
  void add_edge(const int id_src, const int id_dst) { add_edge({id_src, id_dst}); };
  void add_edge(const int id_src, const int id_dst, const Weight w) { add_edge({id_src, id_dst, w}); };
};
template <typename Weight>
ostream &operator<<(ostream &os, const Graph<Weight> &g)
{
  cout << "Graph(" << g.size() << ")"
       << "[" << endl;
  ;
  for (auto &e : g.edges)
    os << " " << e << "," << endl;
  cout << "]";
  return os;
}

//----------------------------------------------------------

template <typename Weight>
void Vertex<Weight>::add_edge(const Edge<Weight> &e)
{
  edges.push_back(e);
  ids_dst.push_back(e.id_dst);
}

template <typename Weight>
bool operator<(const Edge<Weight> &e1, const Edge<Weight> &e2)
{
  return e1.weight != e2.weight ? e1.weight > e2.weight : // !!INVERSE!!
             e1.id_src != e2.id_src ? e1.id_src < e2.id_src : e1.id_dst < e2.id_dst;
}

template <typename Weight>
Graph<Weight>::Graph(const int nvertices)
{
  for (int id = 0; id < nvertices; id++)
    vertices.emplace_back(id);
}
template <typename Weight>
void Graph<Weight>::add_edge(const Edge<Weight> &e)
{
  edges.push_back(e);
  vertices[e.id_src].add_edge(e);
}

// Graph.h end----------------------------------------------
template <typename Weight>
vector<Weight> dijkstra(const Graph<Weight> &g, const int id_start, const Weight INF)
{
  using Pwi = pair<Weight, int>;
  const int n = (int)g.vertices.size();
  vector<Weight> d(n, INF);
  d[id_start] = 0;
  vector<bool> is_used(n, false);
  priority_queue<Pwi, vector<Pwi>, greater<Pwi>> que;

  que.push(Pwi(0, id_start));
  while (!que.empty())
  {
    const int id_src = que.top().second; // que.top().first >= d[id_src]
    que.pop();

    if (is_used[id_src])
      continue;
    is_used[id_src] = true;

    auto test = g.vertices[id_src];
    for (const auto &edge : g.vertices[id_src].edges)
    {
      const int id_dst = edge.id_dst;
      if (d[id_dst] > d[id_src] + edge.weight)
      {
        d[id_dst] = d[id_src] + edge.weight;
        que.push(Pwi(d[id_dst], id_dst));
      }
    }
  }

  return d;
}

const int A_max = 50;
int N, M, S;
int s_max;

int pii_to_int(pii p, int second_max = s_max + 1)
{
  return p.first * second_max + p.second;
}

void solve()
{
  cin >> N >> M >> S;
  s_max = M * A_max;
  Graph<ll> g(pii_to_int({N, 0}));
  rep(j, M)
  {
    int U, V, A, B;
    cin >> U >> V >> A >> B, U--, V--;
    forfl(s, A, s_max) g.add_edge(pii_to_int({U, s}), pii_to_int({V, s - A}), B);
    forfl(s, A, s_max) g.add_edge(pii_to_int({V, s}), pii_to_int({U, s - A}), B);
  }
  rep(i, N)
  {
    int C, D;
    cin >> C >> D;
    forfl(s, 0, s_max - 1) g.add_edge(pii_to_int({i, s}), pii_to_int({i, min(s + C, s_max)}), D);
  }

  auto d = dijkstra(g, pii_to_int({0, min(S, s_max)}), llinf / 2);
  forbe(i, 1, N)
  {
    ll d_i_min = llinf;
    forfl(s, 0, s_max) chmin(d_i_min, d[pii_to_int({i, s})]);
    cout << d_i_min << endl;
  }
}

int main()
{
  // srand(time(0));
  cout << fixed << setprecision(15);

  solve();
  return 0;
}


Measured memory_bytes: 86212