#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <climits>

constexpr int SINT_MAX = std::numeric_limits<int>::max();
constexpr int SINT_MIN = std::numeric_limits<int>::min();
constexpr long long SLL_MAX = std::numeric_limits<long long>::max();
constexpr long long SLL_MIN = std::numeric_limits<long long>::min();

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;


template<class T>
T choose(bool b, T t, T f)
{
    if (b) return t;
    else return f;    
}

const char *YesNo(bool b)
{
    return choose(b, "Yes", "No");
}

const char *YESNO(bool b)
{
    return choose(b, "YES", "NO");
}

template<class NumT>
NumT diffabs(NumT l, NumT r)
{
    if (l < r) return r-l;
    else return l-r;    
}

struct myinout_t {} io;

template<class T>
myinout_t &operator >>(myinout_t &my, T &i)
{
    cin >> i;
    return my;
}

myinout_t &operator >>(myinout_t &my, int &i)
{
    int r = scanf("%d", &i);
    if (r != 1) exit(EXIT_FAILURE);
    return my;
}

myinout_t &operator >>(myinout_t &my, ll &i)
{
    int r = scanf("%lld", &i);
    if (r != 1) exit(EXIT_FAILURE);
    return my;
}

template<class T>
myinout_t &operator <<(myinout_t &my, const T &i)
{
    cout << i;
    return my;
}

myinout_t &operator <<(myinout_t &my, int i)
{
    printf("%d", i);
    return my;
}

myinout_t &operator <<(myinout_t &my, ll i)
{
    printf("%lld", i);
    return my;
}

myinout_t &operator <<(myinout_t &my, double i)
{
    printf("%.20f", i);
    return my;
}

constexpr char BR = '\n';


///////////////////////////////////////////////////
#include <queue>
#include <tuple>


int main()
{
    int N, M, S;
    io >> N >> M >> S;

    int A[50][50], B[50][50];
    for (int i = 0; i < 50; i++)
        for (int j = 0; j < 50; j++)
            A[i][j] = B[i][j] = 0;            
        
    
    for (int i = 0; i < M; i++)
    {
        int u, v, a, b;
        io >> u >> v >> a >> b;
        --u; --v;
        A[u][v] = A[v][u] = -a;
        B[u][v] = B[v][u] = b;
    }
    for (int i = 0; i < N; i++)
    {
        int a, b;
        io >> a >> b;
        A[i][i] = a;
        B[i][i] = b;
    }
    
    constexpr int SILVER_MAX = 2600;
    vvll dp(N, vll(SILVER_MAX, SLL_MAX));
    vvb visited(N, vb(SILVER_MAX, false));

    S = min(S, SILVER_MAX - 1);
    dp[0][S] = 0;

    using TP = tuple<ll,int,int>;
    priority_queue<TP, vector<TP>, greater<TP>> q;
    q.emplace(0, 0, S);
    while(q.size())
    {
        auto [cost, node, silver] = q.top(); q.pop();
        if (visited[node][silver]) continue;
        visited[node][silver] = true;

        for (int next = 0; next < 50; next++)
        {
            int a = A[node][next], b = B[node][next];
            if (b && silver+a >= 0 && silver+a < SILVER_MAX)
            {
                if (dp[next][silver+a] > dp[node][silver] + b)
                {
                    dp[next][silver+a] = dp[node][silver] + b;
                    q.emplace(dp[next][silver+a], next, silver+a);
                }
            }
        }
    }

    for (int i = 1; i < N; i++)
    {
        ll min_ele = *min_element(begin(dp[i]), end(dp[i]));
        io << min_ele << BR;
    }
}


Measured memory_bytes: 6376