// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long

#define int long long

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);

using namespace std;



const int N=55;

const int MAX_S=5004;

vector<tuple<int,int,int>>edges[N];

int n,m,S;

vector<pair<int,int>>_exchange;



void dijkstra(int s)

{

  vector<vector<ll>>dist(n,vector<ll>(MAX_S,1e15));

  dist[s][S]=0;

  priority_queue< pair<ll,pair<int,int>>, vector<pair<ll,pair<int,int>>>,greater< pair<ll,pair<int,int>> > >pq; //{dist,{src,silver_coins}}

  pq.push({0,{s,S}});



  while(!pq.empty()){

    int curr_dist=pq.top().first;

    int node=pq.top().second.first;

    int silver=pq.top().second.second;

    pq.pop();

    if(dist[node][silver]<curr_dist)  continue;



    for(auto x:edges[node]){

      if(get<1>(x)<=silver){

        if( dist[get<0>(x)][silver-get<1>(x)] > dist[node][silver]+get<2>(x) ){

          dist[get<0>(x)][silver-get<1>(x)] = dist[node][silver]+get<2>(x);

          pq.push({dist[get<0>(x)][silver-get<1>(x)],{get<0>(x),silver-get<1>(x)}});

        }

      }

    }

    int new_s=min(MAX_S-1,silver+_exchange[node].first);

    if(dist[node][new_s]>dist[node][silver]+_exchange[node].second){

      dist[node][new_s]=dist[node][silver]+_exchange[node].second;

      pq.push({dist[node][new_s],{node,new_s}});

    }

  }



  for(int i=1;i<n;i++){

    int ans=1e15;

    for(int k=0;k<MAX_S;k++){

      ans=min(ans,dist[i][k]);

    }

    cout<<ans<<"\n";

  }

}

signed main(){

  fastio

  cin>>n>>m>>S;

  S=min(S,MAX_S);  //check with bigger limits

  for(int i=0;i<m;i++){

    int u,v,cost_req,time_req;cin>>u>>v>>cost_req>>time_req;

    u--;v--;

    edges[u].emplace_back(v,cost_req,time_req);

    edges[v].emplace_back(u,cost_req,time_req);

  }

  for(int i=0;i<n;i++){

    int silver,time;cin>>silver>>time;

    _exchange.emplace_back(silver,time);

  }

  dijkstra(0);

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.718202788367271x):
#include<bits/stdc++.h>

#define ll long long

#define int long long

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);

using namespace std;



const int N=55;

const int MAX_S=2501;

vector<tuple<int,int,int>>edges[N];

int n,m,S;

vector<pair<int,int>>_exchange;



void dijkstra(int s)

{

  vector<vector<ll>>dist(n,vector<ll>(MAX_S,1e15));

  dist[s][S]=0;

  priority_queue< pair<ll,pair<int,int>>, vector<pair<ll,pair<int,int>>>,greater< pair<ll,pair<int,int>> > >pq; //{dist,{src,silver_coins}}

  pq.push({0,{s,S}});



  while(!pq.empty()){

    int curr_dist=pq.top().first;

    int node=pq.top().second.first;

    int silver=pq.top().second.second;

    pq.pop();

    if(dist[node][silver]<curr_dist)  continue;



    for(auto x:edges[node]){

      if(get<1>(x)<=silver){

        if( dist[get<0>(x)][silver-get<1>(x)] > dist[node][silver]+get<2>(x) ){

          dist[get<0>(x)][silver-get<1>(x)] = dist[node][silver]+get<2>(x);

          pq.push({dist[get<0>(x)][silver-get<1>(x)],{get<0>(x),silver-get<1>(x)}});

        }

      }

    }

    int new_s=min(MAX_S-1,silver+_exchange[node].first);

    if(dist[node][new_s]>dist[node][silver]+_exchange[node].second){

      dist[node][new_s]=dist[node][silver]+_exchange[node].second;

      pq.push({dist[node][new_s],{node,new_s}});

    }

  }



  for(int i=1;i<n;i++){

    int ans=1e15;

    for(int k=0;k<MAX_S;k++){

      ans=min(ans,dist[i][k]);

    }

    cout<<ans<<"\n";

  }

}

signed main(){

  fastio

  cin>>n>>m>>S;

  S=min(S,MAX_S-1);  //check with bigger limits

  for(int i=0;i<m;i++){

    int u,v,cost_req,time_req;cin>>u>>v>>cost_req>>time_req;

    u--;v--;

    edges[u].emplace_back(v,cost_req,time_req);

    edges[v].emplace_back(u,cost_req,time_req);

  }

  for(int i=0;i<n;i++){

    int silver,time;cin>>silver>>time;

    _exchange.emplace_back(silver,time);

  }

  dijkstra(0);

  return 0;

}