#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> lll;

const ll MOD = 1000000007;
const ll INF = 1e9+5;
const double eps = 1e-7;
const double PI = acos(-1.0);

#define FOR(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define RFOR(i,a,b) for(long long i = (long long)(a); i >= (long long)(b); i--)
#define ull unsigned long long
#define deb(x )     cerr << #x << " = "<< x << endl;
#define endl    "\n"
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define fill(x, y) memset(x, y, sizeof(y))
#define all(x) (x).begin(), (x).end()
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define verify(x) if(x >= MOD) x -= MOD;

inline void debug_vi(vi a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void debug_vll(vll a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void print_case(int tn) {cout<<"Case #"<<tn<<": ";}

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
using maxpq = priority_queue<T>;
/*----------------------------------------------------------------------*/

const int nax = 51;
int n,m,s;
ll dp[nax][5100]; // dp[i][j]: min time to get to vertex i having j coins in hand.
vector<iii> g[nax]; // nxt, {coins, minutes}
int esum = 0;
vii coincounter; // goldtosilver, minutes

void solve() {
    minpq<pair<ll, ii>> pq; // minutes, vertex and coins in hand.
    FOR(boughttimes, 0, esum + 1) {
        ll starttime = 1LL * boughttimes * coincounter[0].ss;
        ll startingcoins = min(esum * 1LL, boughttimes * coincounter[0].ff + s);

        dp[0][startingcoins] = starttime;
        pq.push({starttime, {0, startingcoins}});

        if(boughttimes * 1LL * coincounter[0].ff + s > esum) break;
    }

    while(!pq.empty()) {
        auto curr = pq.top(); pq.pop();
        ll mins = curr.ff; int v, silvers;
        tie(v, silvers) = curr.ss;

        if(dp[v][silvers] < mins) continue;
        for(auto nxt : g[v]) {
            int nxtv = nxt.ff; int coins, timecost;
            tie(coins, timecost) = nxt.ss;

            FOR(boughttimes, 0, esum + 1) {
                ll buyingtime = 1LL * boughttimes * coincounter[v].second;
                ll totalsilver = silvers + 1LL * boughttimes * coincounter[v].first;
                if(totalsilver < coins) continue;
                ll nxtsilver = min(1LL * esum, totalsilver - coins);

                ll newdist = dp[v][silvers] + buyingtime + timecost;
                if(dp[nxtv][nxtsilver] > newdist) {
                    dp[nxtv][nxtsilver] = newdist;
                    pq.push({newdist, {nxtv, nxtsilver}});
                }

                if(totalsilver - coins > esum) break;
            }
        }
    }
}

int main(){
    std::ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    cin>>n>>m>>s;
    int u,v,a,b;
    FOR(i, 0, m) {
        cin>>u>>v>>a>>b; u--; v--;
        g[u].push_back({v, {a, b}});
        g[v].push_back({u, {a, b}});
        esum += a;
    }
    coincounter.resize(n);
    FOR(i, 0, n) {
        cin>>coincounter[i].ff >> coincounter[i].ss;
    }
    FOR(i, 0, n) {
        FOR(j, 0, esum + 1) {
            dp[i][j] = (1e18 + 1);
        }
    }
    solve();
    FOR(i, 1, n) {
        ll res = LONG_LONG_MAX;
        FOR(j, 0, esum + 1) {
            res = min(res, dp[i][j]);
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 37396