// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)

#define chmax(a, b) a = max(a, b)

#define chmin(a, b) a = min(a, b)

#define fi first

#define se second

#define INF 1000000009

#define LLINF 1000000000000000009LL

#define MAX 2505LL

using ll = long long;

typedef pair<ll,ll>P;

typedef pair<P,P>Q;

vector<Q>node[59];

ll min_cost[59][2509];



int main(){

  ll n,m,s;

  cin>>n>>m>>s;

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

    rep(j,MAX+1){

      min_cost[i][j]=LLINF;

    }

  }

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

    ll s,t,a,b;

    cin>>s>>t>>a>>b;

    s--;t--;

    node[s].push_back(Q(P(t,a),P(b,0)));

    node[t].push_back(Q(P(s,a),P(b,0)));

  }

  vector<ll>c(n),d(n);

  rep(i,n)cin>>c[i]>>d[i];



  priority_queue<Q,vector<Q>,greater<Q> >pq;

  pq.push(Q(P(0,0),P(min(s,MAX),0)));

  min_cost[0][min(s,MAX)]=0;



  while(!pq.empty()){

    Q now=pq.top();pq.pop();

    ll cost=now.fi.fi;

    int pos=now.fi.se;

    ll sil=now.se.fi;

    if(sil+c[pos]<=MAX&&cost+d[pos]<min_cost[pos][sil+c[pos]]){

      chmin(min_cost[pos][sil+c[pos]],cost+d[pos]);

      pq.push(Q(P(cost+d[pos],pos),P(sil+c[pos],0)));

    }

    for(int i=0;i<node[pos].size();i++){

      int next=node[pos][i].fi.fi;

      ll a=node[pos][i].fi.se;

      ll b=node[pos][i].se.fi;

      if(sil-a>=0 && cost+b<min_cost[next][sil-a]){

        chmin(min_cost[next][sil-a],cost+b);

        pq.push(Q(P(cost+b,next),P(sil-a,0)));

      }

    }

  }



  rep2(i,1,n){

    ll ans=LLINF;

    rep(j,MAX){

      chmin(ans,min_cost[i][j]);

    }

    cout<<ans<<endl;

  }

  return(0);

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)

#define chmax(a, b) a = max(a, b)

#define chmin(a, b) a = min(a, b)

#define fi first

#define se second

#define INF 1000000009

#define LLINF 1000000000000000009LL

using ll = long long;

const int MAX_N = 59;

const int MAX_S = 2509;



struct Edge {

  int to, a, b;

  Edge(int to, int a, int b) : to(to), a(a), b(b) {}

};



struct Data {

  int v, s;

  ll dist;

  Data(int v, int s, ll dist) : v(v), s(s), dist(dist) {}

  bool operator<(const Data& a) const {

    return dist > a.dist;

  }

};



vector<Edge> g[MAX_N];

ll dp[MAX_N][MAX_S+2];



int main() {

  int n, m, s;

  cin >> n >> m >> s;

  rep(i,n)rep(j,MAX_S+2) dp[i][j] = LLINF;

  rep(i,m) {

    int u, v, a, b;

    cin >> u >> v >> a >> b;

    u--; v--;

    g[u].emplace_back(v, a, b);

    g[v].emplace_back(u, a, b);

  }

  vector<int> c(n), d(n);

  rep(i,n) cin >> c[i] >> d[i];

  s = min(s, MAX_S);



  priority_queue<Data> pq;

  auto push = [&](int v, int s, ll dist) {

    if(s < 0) return;

    if(dp[v][s] <= dist) return;

    dp[v][s] = dist;

    pq.emplace(v, s, dist);

  };

  push(0, s, 0);



  while (!pq.empty()) {

    Data dat = pq.top(); pq.pop();

    int v = dat.v;

    int s = dat.s;

    ll dist = dat.dist;

    {

      int ns = min(s+c[v], MAX_S);

      push(v, ns, dist+d[v]);

    }

    for (auto u : g[v]) {

      push(u.to, s-u.a, dist+u.b);

    }

  }



  rep2(i,1,n) {

    ll ans = LLINF;

    rep(j, MAX_S) {

      chmin(ans, dp[i][j]);

    }

    cout << ans << endl;

  }



  return(0);

}






// Fastest known solution for this problem: