#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF (1LL<<50)

struct edge{int from,to; int silver; int wait;};
struct vertex{int silver, wait;};

int N, M, S;
vertex V[50];
vector<edge> E[50];

int dp[50][5100*2];

signed main() {
  cin >> N >> M >> S;
  S = min(5000LL, S);
  for(int i=0; i<M; i++) {
    int u,v,a,b;
    cin >> u >> v >> a >> b;
    u--, v--;
    edge uv, vu;
    uv.from = u;
    uv.to = v;
    uv.silver = a;
    uv.wait = b;
    vu.from = v;
    vu.to = u;
    vu.silver = a;
    vu.wait = b;
    E[u].push_back(uv);
    E[v].push_back(vu);
  }
  for(int i=0; i<N; i++) { 
    cin >> V[i].silver >> V[i].wait;
    V[i].silver = min(5000LL, V[i].silver);
  }

  for(int i=0; i<N; i++) for(int j=0; j<=5099; j++) { dp[i][j] = INF; }

  dp[0][S] = 0;
  for(int s=S+V[0].silver, wait=V[0].wait; s<=5000; s+=V[0].silver) {
    dp[0][s] = wait;
    wait += V[0].wait;
    //cerr << s << "\t" << dp[0][s] << endl;
  }

  queue<int> q;
  q.push(0);
  while(q.size()) {
    int v = q.front(); q.pop();

    for(int s=0; s<=5000; s++) {
      for(int s2=s+V[v].silver, w=V[v].wait; s2<=5000; s2+=V[v].silver) {
        dp[v][s2] = min(dp[v][s2], dp[v][s] + w);
        w += V[v].wait;
      }
    }

    for(auto e : E[v]) {
      bool mada = true;
      for(int s=0; s+e.silver<=5000; s++) {
        if(dp[e.to][s] > dp[e.from][s + e.silver] + e.wait) {
          dp[e.to][s] = min(dp[e.to][s], dp[e.from][s + e.silver] + e.wait);
          if(mada) {
            q.push(e.to);
            mada=false;
          }
        }
      }
    }
  }

  for(int v=1; v<N; v++) {
    int ans = INF;
    for(int s=0; s<=5000; s++) {
      ans = min(ans, dp[v][s]);
    }
    cout << ans << endl;
  }

}
