#include <memory.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

#define MOD 1000000007

struct elem
{
    long long int time;
    long long int money;
    int now;

    bool operator<(const elem &elem) const
    {
        return elem.time < time;
    }
};

int main()
{
    int n, m, s;
    cin >> n >> m >> s;
    pair<int, int> graph[50][50] = {};
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            graph[i][j] = make_pair(MOD, MOD);
        }
    }
    for (int i = 0; i < m; i++)
    {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        graph[u][v] = make_pair(a, b);
        graph[v][u] = make_pair(a, b);
    }
    int c[50];
    int d[50];
    for (int i = 0; i < n; i++)
    {
        cin >> c[i] >> d[i];
    }
    if (s >= 5000)
    {
        priority_queue<pair<long long int, int>> qu;
        vector<long long int> res(n, pow(MOD, 2));
        qu.push(make_pair(0, 0));
        res[0] = 0;
        while (!qu.empty())
        {
            long long int c = -(qu.top()).first;
            int now = (qu.top()).second;
            qu.pop();
            if (c > res[now])
                continue;
            for (int next = 0; next < n; next++)
            {
                if (graph[now][next] == make_pair(MOD, MOD))
                    continue;
                long long int nextc = c + graph[now][next].second;
                if (res[next] > nextc)
                {
                    res[next] = nextc;
                    qu.push(make_pair(-nextc, next));
                }
            }
        }
        for (int i = 1; i < n; i++)
        {
            cout << res[i] << endl;
        }
    }
    else
    {
        priority_queue<elem> qu;
        vector<vector<long long int>> res(n, vector<long long int>(5010, pow(MOD, 2)));
        qu.push(elem{0, s, 0});
        res[0][s] = 0;
        while (!qu.empty())
        {
            elem e = qu.top();
            qu.pop();
            long long int time = e.time;
            long long int money = e.money;
            int now = e.now;
            if (time > res[now][money])
                continue;
            if (money + c[now] <= 5000)
            {
                long long int nexttime = time + d[now];
                long long int nextmoney = money + c[now];
                if (res[now][nextmoney] > nexttime)
                {
                    res[now][nextmoney] = nexttime;
                    qu.push(elem{nexttime, nextmoney, now});
                }
            }
            for (int next = 0; next < n; next++)
            {
                if (graph[now][next] == make_pair(MOD, MOD))
                    continue;
                long long int nexttime = time + graph[now][next].second;
                long long int nextmoney = money - graph[now][next].first;
                if (nextmoney >= 0 && res[next][nextmoney] > nexttime)
                {
                    res[next][nextmoney] = nexttime;
                    qu.push(elem{nexttime, nextmoney, next});
                }
            }
        }
        for (int i = 1; i < n; i++)
        {
            long long int ans = pow(MOD, 2);
            for (int j = 0; j <= 5000; j++)
            {
                ans = min(ans, res[i][j]);
            }
            cout << ans << endl;
        }
    }
}

Measured memory_bytes: 11408