// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>



#define MAXN 55

#define MAXSILVER 2500



using ll = long long int;

std::vector< std::vector< std::pair<int, std::pair<int, ll> > > > g(MAXN);

//silver, transaction time for each gold

std::pair<ll, ll> trans[MAXN];

ll dist[MAXN][MAXSILVER];



std::pair<ll, std::pair<int, int> > mp(ll x, int y, int z)

{

    return std::make_pair(x, std::make_pair(y, z));

}



void solve(int start, int silver)

{

    std::priority_queue< std::pair<ll, std::pair<int, int> >,

                        std::vector< std::pair<ll, std::pair<int, int> > >,

                            std::greater<std::pair<ll, std::pair<int, int> > > > s;

    s.push(mp(0, start, silver));

    dist[start][silver] = 0;



    while (!s.empty())

    {

        std::pair<ll, std::pair<int, int> > top = s.top();

        s.pop();

        ll curdist = top.first;

        int v = top.second.first, silv = top.second.second;

        if (curdist > dist[v][silv]) continue;

//        if (s.size() > 100000) std::cout << s.size() << "\n";



        if (trans[v].first + silv <= MAXSILVER-2)

        {

            ll t = trans[v].second;

            int nextsilv = silv + trans[v].first;

            if (dist[v][silv] + t < dist[v][nextsilv])

            {

                dist[v][nextsilv] = dist[v][silv] + t;

                s.push(mp(curdist + t, v, nextsilv));

            }

        }



        for (std::pair< int, std::pair<int, int> > nxtpr : g[v])

        {

            int nxt = nxtpr.first;

            int silvtaken = nxtpr.second.first;

            ll timetaken = nxtpr.second.second;



            if (silv - silvtaken < 0) continue;

            int nxtsilver = silv - silvtaken;



            if (dist[v][silv] + timetaken < dist[nxt][nxtsilver])

            {

                dist[nxt][nxtsilver] = dist[v][silv] + timetaken;

                s.push(mp(curdist + timetaken, nxt, nxtsilver));

            }

        }

    }

}



int main()

{

    int n, m, s;

    std::cin >> n >> m >> s;



    s = std::min(s, MAXSILVER-3);

    int x, y, a, b;

    while (m--)

    {

        std::cin >> x >> y >> a >> b; --x; --y;

        g[x].push_back(std::make_pair(y, std::make_pair(a, b)));

        g[y].push_back(std::make_pair(x, std::make_pair(a, b)));

    }



    for (int i = 0; i < n; ++i)

        std::cin >> trans[i].first >> trans[i].second;



    for (int i = 0; i < n; ++i)

        for (int j = 0; j < MAXSILVER-2; ++j)

            dist[i][j] = 1e15;

    solve(0, s);



    for (int i = 1; i < n; ++i)

    {

        ll ans = 1e15;

        for (int j = 0; j < MAXSILVER-2; ++j)

        {

            ans = std::min(ans, dist[i][j]);

        }



        std::cout << ans << "\n";

    }

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>



#define MAXN 55

#define MAXSILVER 2500



using ll = long long int;

std::vector< std::vector< std::pair<int, std::pair<int, ll> > > > g(MAXN);

//silver, transaction time for each gold

std::pair<ll, ll> trans[MAXN];

ll dist[MAXN][MAXSILVER];



struct Node

{

    ll distance;

    int y, z;



    Node(ll distance, int y, int z) {this->distance = distance; this->y=y; this->z = z;}



    bool operator<(const Node& other) const

    {

        return distance < other.distance;

    }

    bool operator>(const Node& other) const

    {

        return distance > other.distance;

    }

};



std::pair<ll, std::pair<int, int> > mp(ll x, int y, int z)

{

    return std::make_pair(x, std::make_pair(y, z));

}



void solve(int start, int silver)

{

    std::priority_queue< Node,

                        std::vector< Node >,

                            std::greater<Node> > s;

    s.push(Node(0, start, silver));

    dist[start][silver] = 0;



    while (!s.empty())

    {

        Node top = s.top();

        s.pop();

        ll curdist = top.distance;

        int v = top.y, silv = top.z;

        if (curdist > dist[v][silv]) continue;

//        if (s.size() > 100000) std::cout << s.size() << "\n";



        if (trans[v].first + silv <= MAXSILVER-2)

        {

            ll t = trans[v].second;

            int nextsilv = silv + trans[v].first;

            if (dist[v][silv] + t < dist[v][nextsilv])

            {

                dist[v][nextsilv] = dist[v][silv] + t;

                s.push(Node(curdist + t, v, nextsilv));

            }

        }



        for (std::pair< int, std::pair<int, int> > nxtpr : g[v])

        {

            int nxt = nxtpr.first;

            int silvtaken = nxtpr.second.first;

            ll timetaken = nxtpr.second.second;



            if (silv - silvtaken < 0) continue;

            int nxtsilver = silv - silvtaken;



            if (dist[v][silv] + timetaken < dist[nxt][nxtsilver])

            {

                dist[nxt][nxtsilver] = dist[v][silv] + timetaken;

                s.push(Node(curdist + timetaken, nxt, nxtsilver));

            }

        }

    }

}



int main()

{

    int n, m, s;

    std::cin >> n >> m >> s;



    s = std::min(s, MAXSILVER-3);

    int x, y, a, b;

    while (m--)

    {

        std::cin >> x >> y >> a >> b; --x; --y;

        g[x].push_back(std::make_pair(y, std::make_pair(a, b)));

        g[y].push_back(std::make_pair(x, std::make_pair(a, b)));

    }



    for (int i = 0; i < n; ++i)

        std::cin >> trans[i].first >> trans[i].second;



    for (int i = 0; i < n; ++i)

        for (int j = 0; j < MAXSILVER-2; ++j)

            dist[i][j] = 1e15;

    solve(0, s);



    for (int i = 1; i < n; ++i)

    {

        ll ans = 1e15;

        for (int j = 0; j < MAXSILVER-2; ++j)

        {

            ans = std::min(ans, dist[i][j]);

        }



        std::cout << ans << "\n";

    }

}


// Fastest known solution for this problem: