// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
#include <time.h>
#include <iomanip>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
typedef std::vector<ll> VI;
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define SZ(x) ((int)((x).size()))
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 55;
struct EDGE
{
    int next, to, a, b;
} edge[maxn << 2];
int head[maxn], tot;
inline void addedge(int u, int v, int a, int b)
{
    edge[tot] = {head[u], v, a, b};
    head[u] = tot++;
}
ll dis[maxn][maxn * maxn];
int c[maxn], d[maxn];
bool inque[maxn][maxn * maxn];
void spfa(int s,int S)
{
    memset(dis, 0x3f, sizeof dis);
    dis[s][S] = 0;
    queue<pii> q;
    inque[s][S] = 1;
    q.push(pii(s, S));
    while (!q.empty())
    {
        pii u = q.front();
        q.pop();
        inque[u.first][u.second] = 0;
        for (int i = head[u.first]; ~i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (u.second >= edge[i].a && dis[v][u.second - edge[i].a] > dis[u.first][u.second] + edge[i].b)
            {
                dis[v][u.second - edge[i].a] = dis[u.first][u.second] + edge[i].b;
                if (!inque[v][u.second - edge[i].a])
                {
                    q.push(pii(v, u.second - edge[i].a));
                    inque[v][u.second - edge[i].a] = 1;
                }
            }
        }
        if (dis[u.first][min(u.second + c[u.first], 2500)] > dis[u.first][u.second] + d[u.first])
        {
            dis[u.first][min(u.second + c[u.first], 2500)] = dis[u.first][u.second] + d[u.first];
            if (!inque[u.first][min(u.second + c[u.first], 2500)])
            {
                q.push(pii(u.first, min(u.second + c[u.first], 2500)));
                inque[u.first][min(u.second + c[u.first], 2500)] = 1;
            }
        }
    }
}
int main()
{
    int n, m, S;
    int u, v, a, b;
    memset(head, -1, sizeof head);
    read(n), read(m), read(S);
    for (int i = 0; i < m; ++i)
    {
        read(u), read(v), read(a), read(b);
        addedge(u, v, a, b);
        addedge(v, u, a, b);
    }
    for (int i = 1; i <= n; ++i)
    {
        read(c[i]);
        read(d[i]);
    }
    spfa(1, min(S, 2500));
    for (int i = 2; i <= n;++i)
    {
        ll res = INF << 1;
        for (int j = 0; j <= 2500; ++j)
        {
            res = min(res, dis[i][j]);
        }
        printf("%lld\n", res);
    }
}

Measured memory_bytes: 5400