#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;
typedef pair<ll,P> Node;
ll N,M,S;
struct Edge{
    ll to,cost,time;
};
ll d[51][2501];
ll C[51],D[51];
vector<Edge> edgeList[51];
int main(){
    cin>>N>>M>>S;
    for(ll i=0;i<M;i++){
        ll u,v,a,b;
        cin>>u>>v>>a>>b;
        u--;v--;
        edgeList[u].push_back(Edge{v,a,b});
        edgeList[v].push_back(Edge{u,a,b});
    }
    for(ll i=0;i<N;i++){
        cin>>C[i]>>D[i];
    }
    for(ll i=0;i<N;i++){
        for(ll j=0;j<=50*N;j++){
            d[i][j]=INF;
        }
    }
    priority_queue<Node,vector<Node>,greater<Node>> pq;
    pq.push(Node(0,P(0,min(S,50*N))));
    d[0][min(S,50*N)]=0;
    while(!pq.empty()){
        ll now=pq.top().second.first;
        ll nowS=pq.top().second.second;
        ll nowTime=pq.top().first;
        pq.pop();
        if(nowTime>d[now][nowS])continue;
        for(auto e:edgeList[now]){
            if(nowS-e.cost<0)continue;
            ll newTime=nowTime+e.time;
            if(d[e.to][nowS-e.cost]>newTime){
                d[e.to][nowS-e.cost]=newTime;
                pq.push(Node(newTime,P(e.to,nowS-e.cost)));
            }
        }
        for(ll i=1;nowS+i*C[now]<=50*N;i++){
            ll newTime=nowTime+D[now]*i;
            ll newS=nowS+i*C[now];
            if(d[now][newS] > newTime){
                d[now][newS]=newTime;
                pq.push(Node(newTime,P(now,newS)));
            }
        }
    }
    for(ll i=1;i<N;i++){
        ll ans=INF;
        for(ll j=0;j<=50*N;j++){
            ans=min(ans,d[i][j]);
        }
        cout<<ans<<endl;
    }
    return 0;
}