#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
typedef long long ll;
using ll = long long;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
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; }
const ll INF = 1e18;


template< typename T >
struct Edge {//辺の構造体を作る
    int from,to;
    T cost;
    int idx;//辺の番号

    Edge() = default;//omajinai

    //初期化
    Edge(int from,int to,T cost = 1, int idx =-1):from(from),to(to),cost(cost),idx(idx){}
    
    /*
    operator int() const{ return to; }
    */
};

template< typename T=int >
struct Graph {
    vector< vector< Edge< T > > > g;
    int es;//辺のidに相当

    Graph() = default;

    explicit Graph(int n):g(n),es(0){}//explicitにより値渡しでコンストラクタを呼ばれないようにする

    size_t size() const{
        return g.size();//size関数を使った時にはグラフの大きさを返すようにする
    }

    void add_directed_edge(int from,int to, T cost=1){//有向辺
        g[from].emplace_back(from,to,cost,es++);
    }

    void add_edge(int from,int to,T cost = 1){//無向辺
        g[from].emplace_back(from,to,cost,es);
        g[to].emplace_back(to,from,cost,es++);//esを追加してから++してる
    }

    void read(int M,int padding = -1,bool weighted = false,bool directed=false){
        for(int i=0;i<M;i++){
            int a,b;
            cin >> a >> b;
            a += padding;
            b += padding;
            T c = T(1);//costなしなら1
            if(weighted)cin>>c;
            if(directed)add_directed_edge(a,b,c);
            else add_edge(a,b,c);
        }
    }
};

template< typename T = int >
using Edges = vector< Edge< T > >;


/*重みつきグラフと始点を引数にとり、始点から全頂点間の最短コストを求める
到達出来ない頂点には型の最大値を格納する*/
/*このライブラリを用いることで重みつきグラフの構築さえ行えば
ダイクストラを勝手に行ってくれてとても便利!*/

template< typename T >
vector< T > dijkstra(const Graph< T > &g, int s){
    const auto INF = numeric_limits< T >::max();
    vector< T > dist(g.size(),INF);//始点からの距離を格納

    using Pi = pair< T , int >;
    priority_queue<Pi,vector<Pi>,greater<> >que;
    dist[s]=0;
    que.emplace(dist[s],s);
    while(!que.empty()){
        T cost;
        int idx;
        tie(cost,idx) = que.top();
        que.pop();
        if(dist[idx] < cost)continue;//すでによりコストの低い経路があった場合
        for(auto &e:g.g[idx]){
            auto next_cost = cost + e.cost;
            if(dist[e.to] <= next_cost)continue;
            dist[e.to] = next_cost;
            que.emplace(dist[e.to],e.to);
        }
    }
    return dist;
}



int main(){
    ll n,m,s;
    cin >> n >> m >> s;
    Graph<ll>g(140000);
    rep(i,m){
        ll u,v,a,b;
        cin >> u >> v >> a >> b;
        u--;v--;
        for(int j=a;j<=2500;j++){
            g.add_directed_edge(u+j*n,v+(j-a)*n,b);
            g.add_directed_edge(v+j*n,u+(j-a)*n,b);
        }
    }
    rep(i,n){
        ll c,d;
        cin >> c >> d;
        for(int j=0;j<=2500;j++){
            ll l = min(j+c,2500LL);
            g.add_directed_edge(i+j*n,i+l*n,d);
        }
    }
    s = min(s,2500LL);
    auto dist = dijkstra(g,n*s);
    for(int i=1;i<n;i++){
        ll ans = INF;
        for(int j=0;j<=2500;j++){
            chmin(ans,dist[i+n*j]);
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 30460