#include"bits/stdc++.h"

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF * 300 * 300;
const int MOD = 1e9+7;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

struct Road{
    LL direct;
    LL cost;
    LL time;
};


struct Station {
    LL point;
    LL time;
    LL coin;
    Station(LL point, LL time, LL coin) : point(point), time(time), coin(coin) {}

    // ソート用
    //bool operator <(const Station& rhs) const {
    //    return time < rhs.time;
    //}
    bool operator >(const Station& rhs) const {
        return time > rhs.time;
        /*
        if(time > rhs.time){
            return true;
        }
        else if (time == rhs.time){
            return coin < rhs.coin;
        }
        else{
            return false;
        }
        */
    }
};

const LL coin_max = 2600;

LL add_coin(LL now, LL add){
    return min(now+add,coin_max);
}

void Main()
{
    LL n,m,s;cin>>n>>m>>s;
    vector<vector<Road>> e(n);
    REP(i,m){
        LL u,v,a,b;
        cin>>u>>v>>a>>b;
        u--;v--;
        e[u].PB((Road){v,a,b});
        e[v].PB((Road){u,a,b});
    }
    vector<pair<LL,LL>> ex(n);
    REP(i,n){
        LL c,d;
        cin>>c>>d;
        ex[i]=MP(c,d);
    }

    vector<LL> result(n,-1);
    vector<vector<LL>> flag(n);
    REP(i,n){
        flag[i].resize(coin_max+10,-1);
    }
    priority_queue<Station, vector<Station>, greater<Station>> q;
    q.push(Station(0,0,min(s,coin_max)));


    while(!q.empty()){
        Station now_station = q.top();
        q.pop();
        LL point = now_station.point;
        LL time = now_station.time;
        LL coin = now_station.coin;

        //cerr<<point<<":"<<time<<":"<<coin<<endl;

        if(result[point] == -1){
            result[point] = time;
        }

        bool end_check = true;
        REP(i,n){
            if(result[i] == -1){
                end_check = false;
                break;
            }
        }
        if(end_check){
            break;
        }

        if(flag[point][coin]==-1){
            flag[point][coin]=time;
        }
        else {
            continue;
        }

        for(auto x : e[point]){
            if(coin<x.cost){
                continue;
            }
            if(flag[x.direct][coin-x.cost] == -1 || time + x.time < flag[x.direct][coin-x.cost]){
                q.push(Station(x.direct, time + x.time, coin-x.cost));
            }
        }
        if(flag[point][add_coin(coin,ex[point].first)] == -1 || 
                time + ex[point].second < flag[point][add_coin(coin,ex[point].first)]){
            q.push(Station(point, time + ex[point].second, add_coin(coin,ex[point].first)));
        }
    }

    FOR(i,1,n){
        cout<<result[i]<<endl;
    }
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

Measured memory_bytes: 10512