#include <bits/stdc++.h>
#define ll long long int
#define ld long double
const ll MOD = 998244353;
const ll INF = 1e18;
using namespace std;
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define deb(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define deb(...) 42
#endif
struct point{
    ll dist, u, ind;
    bool operator >(point &a){
        return dist > a.dist;
    }
};

ll dist[51][5005];
ll n, m, s;
ll a[110], b[110], c[110], d[110];
vector<vector<pair<int, int>>> edges;
struct comparitor
{
    bool operator()(const point a, const point b) const
    {
       return (a.dist > b.dist);
    }
};

void djikstra(){
    priority_queue<point, vector<point>, comparitor> pq;
    // priority_queue<point, vector<point>, [](point a, point b) -> bool{
    //     return a.dist > b.dist;
    // }> pq;
    if(s > 5000)    s = 5000;
    int lim = 5001;
    for(int i = 0; i < 51; i++)     for(int j = 0; j < 5001; j++)   dist[i][j] = INF; 
    pq.push({0ll, 0ll, s}), dist[0][s] = 0;

    while(!pq.empty()){
        auto tmp = pq.top();
        pq.pop();
        if(tmp.dist != dist[tmp.u][tmp.ind])    continue;
        //deb(tmp.u, tmp.ind, tmp.dist);
        ll u = tmp.u, dd = dist[tmp.u][tmp.ind];
        for(auto v : edges[u]){
            if(tmp.ind >= a[v.second] and dist[v.first][tmp.ind - a[v.second]] > dd + b[v.second]){
                dist[v.first][tmp.ind - a[v.second]] = dd + b[v.second];
                pq.push({dist[v.first][tmp.ind - a[v.second]], v.first, tmp.ind - a[v.second]});
            }
        }
        if(dist[u][min(5000ll, tmp.ind + c[u])] > dd + d[u])  dist[u][min(5000ll, tmp.ind + c[u])] = dd + d[u], pq.push({dist[u][min(5000ll, tmp.ind + c[u])], u, min(5000ll, tmp.ind + c[u])});
    }
}

main(){    
    #ifdef XOX
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\Input.txt", "r", stdin);
        freopen("D:\\V S Code\\cpp\\competitiveProgramming\\OPT.txt", "w", stdout);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m >> s;

    int u, v;
    edges.resize(n + 1);
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        u--, v--;
        cin >> a[i] >> b[i];
        edges[u].push_back({v, i});
        edges[v].push_back({u, i});
    }

    for(int i = 0; i < n; i++) cin >> c[i] >> d[i];
    djikstra();

    ll ans = 0;
    for(int i = 1; i < n; i++){
        ans = INF;
        for(int j = 0; j <= 5000; j++)  ans = min(ans, dist[i][j]);
        cout << ans << "\n";
    }

}

Measured memory_bytes: 11464