#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>     // tuple<int,char,string> x; みたいに使う
#include <utility>   // pair

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

template <class InputIterator, class T>
bool contains(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// =========ここまでテンプレ============

int main()
{
    ll n;
    ll m;
    ll s;
    cin >> n;
    cin >> m;
    cin >> s;
    // vector<array<ll, 4>> uvab;
    // tuple<ll, ll, ll> toCityTimeSilver;
    vector<set<tuple<ll, ll, ll>>> toCitySilverTimes(n);
    vector<array<ll, 2>> toSelfSilverTimes;
    ll amax = 0;
    for (ll i = 0; i < m; i++)
    {
        ll u;
        ll v;
        ll a;
        ll b;
        cin >> u;
        cin >> v;
        cin >> a;
        cin >> b;
        // uvab.push_back(array{u, v, a, b});
        toCitySilverTimes[u - 1].insert(tuple<ll, ll, ll>{v - 1, a, b});
        toCitySilverTimes[v - 1].insert(tuple<ll, ll, ll>{u - 1, a, b});
        amax = max(amax, a * (n - 1));
        // いらないシルバーは捨てる！！
        s = min(s, amax);
    }
    for (ll i = 0; i < n; i++)
    {
        ll c;
        ll d;
        cin >> c;
        cin >> d;
        // cd.push_back(array{c, d});
        toSelfSilverTimes.push_back(array<ll, 2>{c, d});
    }

    // ここからダイクストラ

    // priority_queue<暫定min時間,都市、銀貨> の初期化
    using node = tuple<ll, ll, ll>; // temporary minimum Time of City, Silver
    priority_queue<node, vector<node>, greater<node>> que;
    que.push(node{0, 0, s});

    // 暫定距離をメモる領域の初期化
    // (city, silver)=>time
    map<tuple<ll, ll>, ll> times;
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j <= amax; j++)
        {
            times.insert({tuple<ll, ll>{i, j}, LLONG_MAX});
        }
    }
    vector<ll> minTimes(n, LLONG_MAX);

    // ダイクストラ実行
    while (!que.empty())
    {
        node x = que.top();
        que.pop();
        ll currentTime = get<0>(x);
        ll currentCity = get<1>(x);
        ll currentSilver = get<2>(x);
        minTimes[currentCity] = min(minTimes[currentCity], currentTime);
        if (currentTime <= times[tuple<ll, ll>{currentCity, currentSilver}])
        {
            times[tuple<ll, ll>{currentCity, currentSilver}] = currentTime;

            // 移動するケースを列挙し、更新可能なら更新してキューに追加
            for (tuple<ll, ll, ll> toCst : toCitySilverTimes[currentCity])
            {
                ll toCity = get<0>(toCst);
                ll costSilver = get<1>(toCst);
                ll costTime = get<2>(toCst);
                if (currentSilver >= costSilver)
                {
                    node destNode = node{currentTime + costTime, toCity, currentSilver - costSilver};
                    if (times[tuple<ll, ll>{get<1>(destNode), get<2>(destNode)}] > currentTime + costTime)
                    {
                        times[tuple<ll, ll>{get<1>(destNode), get<2>(destNode)}] = currentTime + costTime;
                        que.push(destNode);
                    }
                }
            }

            // 両替するケース。更新可能なら更新してキューに追加
            ll venefitSilver = toSelfSilverTimes[currentCity][0];
            ll costTime = toSelfSilverTimes[currentCity][1];
            node destNode = node{currentTime + costTime, currentCity, min(amax, currentSilver + venefitSilver)};
            if (times[tuple<ll, ll>{get<1>(destNode), get<2>(destNode)}] > currentTime + costTime)
            {
                times[tuple<ll, ll>{get<1>(destNode), get<2>(destNode)}] = currentTime + costTime;
                que.push(destNode);
            }
        }
    }
    for (ll i = 1; i < n; i++)
    {
        cout << minTimes[i] << endl;
    }
}

Measured memory_bytes: 13444