#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

template<class T>
bool UpdateMax(T &a, const T &b){
  if(a<b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template<class T>
bool UpdateMin(T &a, const T &b){
  if(a>b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

template<typename CostType>
/// \brief 辺の情報
struct Edge{
  int      to;
  CostType cost;

  Edge(int t, CostType c): to(t), cost(c){
  }
};

template<typename CostType>
class Graph{

private:

  /// \brief adjacent_list_[n]=ノードnの隣接リストを表すvector<Edge>
  std::vector<std::vector<Edge<CostType>>> adjacent_list_;

public:

  /// \brief 頂点数
  const int NODE_SIZE_;

  /// \brief コンストラクタ
  /// \param node_size 頂点数
  explicit Graph(const int node_size): NODE_SIZE_(node_size),
                                       adjacent_list_(node_size){
  }

  /// \brief 有向グラフの辺を生やす
  /// \param from 辺の根本の頂点の番号
  /// \param to 辺の先の頂点の番号
  /// \param cost 辺のコスト
  void SetDirectedEdge(const int from, const int to, const CostType cost){
    adjacent_list_[from].push_back(Edge<CostType>(to, cost));
  }

  /// \brief 無向グラフの辺を生やす
  /// \param node_a 一方の頂点の番号
  /// \param node_b もう一方の頂点の番号
  /// \param cost 辺のコスト
  void
  SetUndirectedEdge(const int node_a, const int node_b, const CostType cost){
    SetDirectedEdge(node_a, node_b, cost);
    SetDirectedEdge(node_b, node_a, cost);
  }

  /// \brief ある頂点の隣接リストを取得
  /// \param node_num 頂点の番号
  /// \return 隣接リスト
  std::vector<Edge<CostType>> GetAdjacentList(int node_num) const{
    return adjacent_list_[node_num];
  }
};

/// \brief ダイクストラ法により，ある頂点からの最短経路を求める
/// \tparam CostType 辺のコストの型
/// \param graph グラフ
/// \param start_node どの頂点から最短経路を求めるか
/// \param INF CostType型で十分大きい値
/// \return グラフの各頂点への最短経路を示す配列(到達不可能なときはINF)，負の辺が入っていた場合はsize0の配列
template<typename CostType>
std::vector<CostType>
Dijkstra(const Graph<CostType>& graph, const int start_node, CostType INF){
  struct Info{
    int      node;
    CostType cost;

    Info(int n, CostType c): node(n), cost(c){
    };

    bool operator>(const Info& another) const{
      return cost > another.cost;
    }
  };

  std::vector<CostType>                                            min_cost
                                                                     (graph
                                                                        .NODE_SIZE_);
  std::priority_queue<Info, std::vector<Info>, std::greater<Info>> pq;
  for(int                                                          i = 0;
      i < min_cost.size(); i++){
    min_cost[i] = (i == start_node) ? 0 : INF;
  }
  pq.push(Info(start_node, 0));

  while(!pq.empty()){
    Info current_info = pq.top();
    pq.pop();
    if(min_cost[current_info.node] != current_info.cost){ continue; }
    const std::vector<Edge<CostType>>
      & adjacency_list = graph.GetAdjacentList(current_info.node);
    for(auto e:adjacency_list){
      if(min_cost[e.to] > min_cost[current_info.node] + e.cost){
        min_cost[e.to] = min_cost[current_info.node] + e.cost;
        pq.push(Info(e.to, min_cost[e.to]));
      }
    }
  }

  return min_cost;

}

const int offset=2501;

int nodeid(int pos,int price){
  return pos*offset+price;
}



int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  lint n,m,s;
  cin>>n>>m>>s;

  Graph<lint> graph(n*offset);
  for(int i=0;i<m;i++){
    lint u,v,a,b;
    cin>>u>>v>>a>>b;
    u--;
    v--;
    for(int from=0;from<=2500;from++){
      lint to = from - a;
      if(to >= 0){
        graph.SetDirectedEdge(nodeid(u,from), nodeid(v,to), b);
        graph.SetDirectedEdge(nodeid(v,from), nodeid(u,to), b);
      }
    }
  }



  for(int node=0;node<n;node++){
    lint c,d;
    cin>>c>>d;
    for(int from=2500;from>=0;from--){
      lint to=from+c;
      if(to<=2500)
      graph.SetDirectedEdge(nodeid(node,from),nodeid(node,to),d);
    }
  }
  const lint INF=INT64_MAX/2;

  vector<lint> result=Dijkstra(graph,nodeid(0,min(s,2500l)),INF);

  for(int node=1;node<n;node++){
    lint tmp_res=INF;
    for(int cost=0;cost<=2500;cost++){
      UpdateMin(tmp_res,result[nodeid(node,cost)]);
    }
    cout<<tmp_res<<endl;
  }





  return 0;
}




Measured memory_bytes: 23760