#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) x
#define WATCH(x) TRACE( cout << #x" = " << x << endl)
#define PRINT(x) TRACE(printf(x))
#define WATCHR(a, b) TRACE( for(auto c = a; c != b;) cout << *(c++) << " "; cout << endl;)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end()); } )
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define rsz resize
#define mp make_pair
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define ft front
#define bk back

#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define per(i,a,b) for(int i = (a); i > (b); --i)
#define trav(a,x) for(auto& a : x)
#define travc(a,x) for(const auto& a : x)

using ll = long long;
using ld = long double;
using db = double;
using str = string;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

constexpr ll MOD = 998'244'353;

constexpr int ms = 2553;
constexpr int mn = 53;

constexpr ll infl = MOD * MOD;

ll dp[mn + 2][ms + 2];
vector< tuple<ll,ll,ll> > g[mn];
pair<ll, ll> cost[mn];
ll ans[mn];
// End of template code

inline void propagate(const ll node, ll remaining_silver_coins) {
    ans[node] = min(ans[node], dp[node][remaining_silver_coins]);
    if( remaining_silver_coins < ms - 1 )
    {
        ll xtra = cost[node].second;
        ll new_coins = min(ms - 1ll, remaining_silver_coins + cost[node].first);
        if(dp[node][remaining_silver_coins] + xtra < dp[node][new_coins]) {
            dp[node][new_coins] = dp[node][remaining_silver_coins] + xtra;
            propagate(node, new_coins);
        }
    }
 
    for(const auto& v : g[node]) {
        ll viz, price, delta_t;
        tie(viz, price, delta_t) = v;
        if(price <= remaining_silver_coins) {
            ll cand = dp[node][remaining_silver_coins] + delta_t;
            if(cand < dp[viz][remaining_silver_coins - price]) {
                dp[viz][remaining_silver_coins - price] = cand;
                propagate(viz, remaining_silver_coins - price);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, s;
    cin >> n >> m >> s;
    
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n * 51; ++j) {
            dp[i][j] = infl;
        }
    }

    for(int i = 0; i < n; ++i) ans[i] = infl;
    for(int i = 0; i < m; ++i)
    {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        --u; --v;
        g[u].emplace_back(v, a, b);
        g[v].emplace_back(u, a, b);
    }

    for(int i = 0; i < n; ++i) cin >> cost[i].first >> cost[i].second;

    dp[0][s] = 0ll;
    propagate(0, s); 
    for(int i = 1; i < n; ++i) cout << ans[i] << '\n';
    return 0;
}

