// 分层图最短路 Dijkstra 算法 O(MlogN)
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N=2e5,M=7e5,B=2450; //B是花费银币的上限
int h[N],to[M],w[M],ne[M],idx;
void add(int a,int b,int c){
  to[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int n,m,s;
int d[N];
bool vis[N];

int get(int u,int j){ //点u有j个币的映射点编号
  return (u-1)*(B+1)+j; //u:1~50,j:0~B,B=2450
}
void dijkstra(){
  memset(d,0x3f,sizeof d); d[get(1,min(s,B))]=0;
  priority_queue<pii,vector<pii>,greater<pii> > q;
  q.push({0,get(1,min(s,B))});
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(vis[u]) continue; vis[u]=1;
    for(int i=h[u]; i; i=ne[i]){
      int v=to[i];
      if(d[v]>d[u]+w[i]){
        d[v]=d[u]+w[i];
        q.push({d[v],v});
      }
    }
  }
}
signed main(){
  cin>>n>>m>>s;
  for(int i=1,u,v,x,t; i<=m; i++){
    cin>>u>>v>>x>>t; //边(u,v)花费x个币和t秒
    for(int j=x; j<=B; j++){
      add(get(u,j),get(v,j-x),t); //u到v的合法映射点连权值为t的边
      add(get(v,j),get(u,j-x),t); //v到u的合法映射点连权值为t的边
    }
  }
  for(int i=1,c,t; i<=n; i++){
    cin>>c>>t; //买c个币,花费t秒
    for(int j=0; j+c<=B; j++){
      add(get(i,j),get(i,j+c),t); //i点拆成等差的映射点连权值为t的边
    }
  }
  dijkstra();
  for(int i=2; i<=n; i++){
    int ans=1e16;
    for(int j=0; j<=B; j++)ans=min(ans,d[get(i,j)]); //答案在点i的映射点中
    cout<<ans<<endl;
  }
}