#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}

vi c,d;
class Dijkstra{
private:
    struct edge { int to, cost, tim;};
    struct node {
        int ind, money;
        bool operator >(node const& other) const {
            return money > other.money;
        }
        bool operator <(node const& other) const {
            return money < other.money;
        }
    };
    typedef pair<int,node> pin;
    vector< vector<edge> > g;
    int n;
    int ma;
public:
    Dijkstra(){};
    Dijkstra(int size){
        n = size;
        g.resize(n);
        ma = n * 50;
    }
    int dist[50][10000];//頂点iに時刻jでいるときの最小コスト
    void add_edge(int a, int b, int cost, int tim){//無向辺
        edge e1 = {b, cost, tim}, e2 = {a, cost, tim};
        g[a].push_back(e1);
        g[b].push_back(e2);//有向辺の場合はここをコメントアウトする
    }
    void calc(int initmon){
        priority_queue< pin, vector<pin>, greater<pin> > q;
        rep(i,n)rep(j,ma)dist[i][j] = LINF;
        int inittime = 0;
        if(initmon > ma)initmon = ma-1;
        while(initmon < ma){
            int co = min(ma-1,initmon);
            dist[0][co] = inittime;
            node no = {0,co};
            q.push(pin(inittime, no));
            //両替
            initmon += c[0];
            inittime += d[0];
        }
        while(!q.empty()){
            pin p = q.top();
            q.pop();
            int now = p.second.ind;
            int mon = p.second.money;
            if(dist[now][mon] < p.first)continue; //更新されていたら何もしない
            //cout << now << " " << mon << " " << p.first << endl;
            for(int i = 0; i < g[now].size(); i++){
                edge e = g[now][i];
                int money = mon - e.cost;
                int nexttime = p.first + e.tim;
                if(money < 0){
                    int t = -money;
                    t = t/c[now];
                    money += t*c[now];
                    nexttime += t*d[now];
                }
                if(money > ma)money = ma-1;
                while(money < ma){
                    if(money >= 0 && dist[e.to][money] > nexttime){
                        dist[e.to][money] = nexttime;
                        node ne = {e.to, money};
                        q.push(pin(dist[e.to][money],ne));
                    }
                    //両替
                    money += c[now];
                    nexttime += d[now];
                }

            }
        }
        loop(i,1,n){
            int ret = LINF;
            rep(j,ma)ret = min(ret, dist[i][j]);
            cout << ret << endl;
        }
    }
};

signed main(void) {
    int n,m,s;
    cin >> n >> m >> s;
    Dijkstra dij(n);
    int wf[50][50];
    rep(i,n)rep(j,n)wf[i][j] = LINF;
    rep(i,n)wf[i][i] = 0;
    rep(i,m){
        int u,v,mon,tim;
        cin >> u >> v >> mon >> tim;
        u--,v--;
        dij.add_edge(u,v,mon,tim);
        wf[u][v] = wf[v][u] = mon;
    }

    rep(k,n)rep(i,n)rep(j,n){
        wf[i][j] = min(wf[i][j],wf[i][k] + wf[k][j]);
    }
    c = d = vi(n);
    rep(i,n)cin >> c[i] >> d[i];
    dij.calc(s);
}


Measured memory_bytes: 53212