// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



template <typename T>

class Graph

{

    void _dfs_toporogical_sort(vector<bool> &visited, const long long n, list<long long> &ret) const

    {

        if (visited[n])

        {

            return;

        }

        visited[n] = true;

        for (auto e : this->edge[n])

        {

            _dfs_toporogical_sort(visited, e.to, ret);

        }

        ret.push_front(n);

    }



    void set_node(const long long N)

    {

        this->node = N + 1;

    }



public:

    struct Edge

    {

        long long to;

        T distance;

        Edge(const long long t, const T d)

        {

            this->to = t;

            this->distance = d;

        }

        bool operator<(const Graph<T>::Edge &e) const

        {

            return this->distance < e.distance;

        }

        bool operator<=(const Graph<T>::Edge &e) const

        {

            return this->distance <= e.distance;

        }

        bool operator>(const Graph<T>::Edge &e) const

        {

            return this->distance > e.distance;

        }

        bool operator>=(const Graph<T>::Edge &e) const

        {

            return this->distance >= e.distance;

        }

        bool operator==(const Graph<T>::Edge &e) const

        {

            return this->distance == e.distance;

        }

    };

    class UnionFind

    {

    public:

        vector<long long> root;



        UnionFind(const long long N)

        {

            this->root = vector<long long>(N + 1, -1);

        }



        long long find_root(const long long A)

        {

            if (this->root[A] < 0)

            {

                return A;

            }

            else

            {

                this->root[A] = find_root(this->root[A]);

            }

            return this->root[A];

        }



        long long size(const long long A)

        {

            return -this->root[find_root(A)];

        }



        bool unite(long long A, long long B)

        {

            A = find_root(A);

            B = find_root(B);

            if (A == B)

            {

                return false;

            }



            if (size(A) < size(B))

            {

                swap(A, B);

            }



            this->root[A] += this->root[B];

            this->root[B] = A;



            return true;

        }



        bool has_same_root(const long long A, const long long B)

        {

            return find_root(A) == find_root(B);

        }

    };

    vector<vector<T>> adjacency_matrix;

    long long node;

    T initial_value;

    vector<vector<Graph<T>::Edge>> edge;



    Graph(const long long N)

    {

        this->set_node(N);

        this->initialize_edge_vector();

    }



    Graph(const long long N, const T init)

    {

        this->set_node(N);

        this->initialize_edge_vector();

        this->set_initial_value(init);

    }



    void set_initial_value(const T init)

    {

        this->initial_value = init;

    }



    void initialize_adjacency_matrix()

    {

        this->adjacency_matrix = vector<vector<T>>(

            this->node, vector<T>(this->node, this->initial_value));

    }



    void initialize_adjacency_matrix(const T init)

    {

        this->set_initial_value(init);

        this->initialize_adjacency_matrix();

    }



    void initialize_edge_vector()

    {

        this->edge = vector<vector<Graph<T>::Edge>>(this->node);

    }



    void update_adjacency_matrix(const long long from, const long long to, const T distance = 1)

    {

        this->adjacency_matrix[from][to] = distance;

    }



    void add_edge(const long long from, const long long to, const T distance = 1)

    {

        this->edge[from].push_back({to, distance});

    }



    // O(V^3)

    // CAUTION: Use adjacency matrix

    vector<vector<T>> run_floyd_warshall() const

    {

        vector<vector<T>> ret(this->adjacency_matrix);

        for (long long i = 0; i < this->node; i++)

        {

            for (long long j = 0; j < this->node; j++)

            {

                for (long long k = 0; k < this->node; k++)

                {

                    ret[j][k] = min(ret[j][k], ret[j][i] + ret[i][k]);

                }

            }

        }

        return ret;

    }



    // O(E)

    // CAUTION: Non-weighted only

    // CAUTION: Use edge vector

    vector<T> run_bfs(const long long from) const

    {

        vector<T> distance(this->node, this->initial_value);

        vector<bool> visited(this->node, false);

        queue<long long> q;

        q.push(from);

        for (long long i = 0; i < this->node && !q.empty(); i++)

        {

            queue<long long> tmp;

            while (!q.empty())

            {

                if (visited[q.front()])

                {

                    q.pop();

                    continue;

                }

                distance[q.front()] = i;

                visited[q.front()] = true;

                for (Graph<T>::Edge e : this->edge[q.front()])

                {

                    if (visited[e.to])

                    {

                        continue;

                    }

                    tmp.push(e.to);

                }

                q.pop();

            }

            q = tmp;

        }

        return distance;

    }



    // O(VE)

    // CAUTION: Use edge vector

    vector<T> run_bellman_ford(const long long from) const

    {

        vector<T> distance(this->node, this->initial_value);

        distance[from] = 0;



        for (long long i = 0; i < this->node - 1; i++)

        {

            for (long long j = 0; j < this->node; j++)

            {

                for (Graph<T>::Edge e : this->edge[j])

                {

                    if (distance[e.to] > distance[j] + e.distance)

                    {

                        distance[e.to] = distance[j] + e.distance;

                    }

                }

            }

        }

        return distance;

    }



    // O(E + VlogV)

    // CAUTION: Use edge vector

    // CAUTION: Node-indices must be [1, N]

    vector<T> run_dijkstra(const long long from) const

    {

        vector<T> distance(this->node, this->initial_value);

        priority_queue<Graph<T>::Edge, vector<Graph<T>::Edge>, greater<Graph<T>::Edge>> queue;

        queue.push(Graph<T>::Edge(from, 0));

        for (long long i = 1; i < this->node && !queue.empty(); i++)

        {

            T d = queue.top().distance;

            long long to = queue.top().to;

            queue.pop();

            if (distance[to] == this->initial_value)

            {

                distance[to] = d;

                for (Graph<T>::Edge e : this->edge[to])

                {

                    if (distance[e.to] == this->initial_value)

                    {

                        queue.push({e.to, e.distance + d});

                    }

                }

            }

            else

            {

                i--;

            }

        }

        return distance;

    }



    // O(ElogV)

    // CAUTION: Use edge vector

    // CAUTION: Node-indices must be [1, N]

    T run_prim() const

    {

        vector<bool> is_visited(this->node, false);

        T cost = 0;

        priority_queue<Graph<T>::Edge, vector<Graph<T>::Edge>, greater<Graph<T>::Edge>> queue;

        queue.push(Graph<T>::Edge(1, 0));

        for (long long i = 1; i < this->node && !queue.empty(); i++)

        {

            T distance = queue.top().distance;

            long long to = queue.top().to;

            queue.pop();

            if (is_visited[to])

            {

                i--;

            }

            else

            {

                cost += distance;

                is_visited[to] = true;

                for (Graph<T>::Edge e : this->edge[to])

                {

                    queue.push({e.to, e.distance});

                }

            }

        }

        return cost;

    }



    // O(ElogV)

    // CAUTION: Use edge vector

    T run_kruskal() const

    {

        T cost = 0;

        vector<pair<Graph<T>::Edge, long long>> edge_from;

        for (long long i = 0; i < this->node; i++)

        {

            for (auto e : this->edge[i])

            {

                edge_from.push_back(make_pair(e, i));

            }

        }

        sort(edge_from.begin(), edge_from.end());



        Graph<T>::UnionFind uf(this->node);

        for (pair<Graph<T>::Edge, long long> e_f : edge_from)

        {

            auto e = e_f.first;

            long long from = e_f.second;

            if (!uf.has_same_root(from, e.to))

            {

                uf.unite(from, e.to);

                cost += e.distance;

            }

        }

        return cost;

    }



    // O(V)

    // CAUTION: Without cycle only

    // CAUTION: Use edge vector

    vector<long long> run_toporogical_sort() const

    {

        list<long long> ret_list;

        vector<bool> visited(this->node, false);

        for (long long i = 0; i < this->node; i++)

        {

            _dfs_toporogical_sort(visited, i, ret_list);

        }



        vector<long long> ret(ret_list.begin(), ret_list.end());

        return ret;

    }

};



int main()

{

    constexpr long long MAX_SILVER = 3000;

    size_t N, M;

    long long S;

    cin >> N >> M >> S;

    S = min(S, MAX_SILVER);



    Graph<pair<long long, long long>> g(N);

    long long U, V, A, B;

    for (size_t i = 0; i < M; i++)

    {

        cin >> U >> V >> A >> B;

        g.add_edge(U, V, make_pair(-A, B));

        g.add_edge(V, U, make_pair(-A, B));

    }



    long long C, D;

    for (size_t i = 1; i <= N; i++)

    {

        cin >> C >> D;

        g.add_edge(i, i, make_pair(C, D));

    }



    long long init = -1;

    vector<vector<long long>> d(N + 1, vector<long long>((size_t)MAX_SILVER + 1, init));

    priority_queue<pair<long long, pair<long long, long long>>, vector<pair<long long, pair<long long, long long>>>, greater<pair<long long, pair<long long, long long>>>> q;

    q.push(make_pair(0, make_pair(1, S)));

    while (!q.empty())

    {

        long long distance = q.top().first;

        long long to = q.top().second.first;

        long long silver = q.top().second.second;

        q.pop();



        if (d[to][silver] == init)

        {

            d[to][silver] = distance;



            for (auto e : g.edge[to])

            {

                long long next_silver = silver + e.distance.first;

                long long next_distance = distance + e.distance.second;

                if (next_silver < 0)

                {

                    continue;

                }

                next_silver = min(next_silver, MAX_SILVER);

                q.push(make_pair(next_distance, make_pair(e.to, next_silver)));

            }

        }

    }

    for (size_t i = 2; i <= N; i++)

    {

        long long ans = LONG_LONG_MAX;

        for (long long a : d[i])

        {

            if (a == init)

            {

                continue;

            }

            ans = min(ans, a);

        }

        cout << ans << endl;

    }

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



template <typename T>

class Graph

{

    void _dfs_toporogical_sort(vector<bool> &visited, const long long n, list<long long> &ret) const

    {

        if (visited[n])

        {

            return;

        }

        visited[n] = true;

        for (auto e : this->edge[n])

        {

            _dfs_toporogical_sort(visited, e.to, ret);

        }

        ret.push_front(n);

    }



    void set_node(const long long N)

    {

        this->node = N + 1;

    }



public:

    struct Edge

    {

        long long to;

        T distance;

        Edge(const long long t, const T d)

        {

            this->to = t;

            this->distance = d;

        }

        bool operator<(const Graph<T>::Edge &e) const

        {

            return this->distance < e.distance;

        }

        bool operator<=(const Graph<T>::Edge &e) const

        {

            return this->distance <= e.distance;

        }

        bool operator>(const Graph<T>::Edge &e) const

        {

            return this->distance > e.distance;

        }

        bool operator>=(const Graph<T>::Edge &e) const

        {

            return this->distance >= e.distance;

        }

        bool operator==(const Graph<T>::Edge &e) const

        {

            return this->distance == e.distance;

        }

    };

    class UnionFind

    {

    public:

        vector<long long> root;



        UnionFind(const long long N)

        {

            this->root = vector<long long>(N + 1, -1);

        }



        long long find_root(const long long A)

        {

            if (this->root[A] < 0)

            {

                return A;

            }

            else

            {

                this->root[A] = find_root(this->root[A]);

            }

            return this->root[A];

        }



        long long size(const long long A)

        {

            return -this->root[find_root(A)];

        }



        bool unite(long long A, long long B)

        {

            A = find_root(A);

            B = find_root(B);

            if (A == B)

            {

                return false;

            }



            if (size(A) < size(B))

            {

                swap(A, B);

            }



            this->root[A] += this->root[B];

            this->root[B] = A;



            return true;

        }



        bool has_same_root(const long long A, const long long B)

        {

            return find_root(A) == find_root(B);

        }

    };

    vector<vector<T>> adjacency_matrix;

    long long node;

    T initial_value;

    vector<vector<Graph<T>::Edge>> edge;



    Graph(const long long N)

    {

        this->set_node(N);

        this->initialize_edge_vector();

    }



    Graph(const long long N, const T init)

    {

        this->set_node(N);

        this->initialize_edge_vector();

        this->set_initial_value(init);

    }



    void set_initial_value(const T init)

    {

        this->initial_value = init;

    }



    void initialize_adjacency_matrix()

    {

        this->adjacency_matrix = vector<vector<T>>(

            this->node, vector<T>(this->node, this->initial_value));

    }



    void initialize_adjacency_matrix(const T init)

    {

        this->set_initial_value(init);

        this->initialize_adjacency_matrix();

    }



    void initialize_edge_vector()

    {

        this->edge = vector<vector<Graph<T>::Edge>>(this->node);

    }



    void update_adjacency_matrix(const long long from, const long long to, const T distance = 1)

    {

        this->adjacency_matrix[from][to] = distance;

    }



    void add_edge(const long long from, const long long to, const T distance = 1)

    {

        this->edge[from].push_back({to, distance});

    }



    // O(V^3)

    // CAUTION: Use adjacency matrix

    vector<vector<T>> run_floyd_warshall() const

    {

        vector<vector<T>> ret(this->adjacency_matrix);

        for (long long i = 0; i < this->node; i++)

        {

            for (long long j = 0; j < this->node; j++)

            {

                for (long long k = 0; k < this->node; k++)

                {

                    ret[j][k] = min(ret[j][k], ret[j][i] + ret[i][k]);

                }

            }

        }

        return ret;

    }



    // O(E)

    // CAUTION: Non-weighted only

    // CAUTION: Use edge vector

    vector<T> run_bfs(const long long from) const

    {

        vector<T> distance(this->node, this->initial_value);

        vector<bool> visited(this->node, false);

        queue<long long> q;

        q.push(from);

        for (long long i = 0; i < this->node && !q.empty(); i++)

        {

            queue<long long> tmp;

            while (!q.empty())

            {

                if (visited[q.front()])

                {

                    q.pop();

                    continue;

                }

                distance[q.front()] = i;

                visited[q.front()] = true;

                for (Graph<T>::Edge e : this->edge[q.front()])

                {

                    if (visited[e.to])

                    {

                        continue;

                    }

                    tmp.push(e.to);

                }

                q.pop();

            }

            q = tmp;

        }

        return distance;

    }



    // O(VE)

    // CAUTION: Use edge vector

    vector<T> run_bellman_ford(const long long from) const

    {

        vector<T> distance(this->node, this->initial_value);

        distance[from] = 0;



        for (long long i = 0; i < this->node - 1; i++)

        {

            for (long long j = 0; j < this->node; j++)

            {

                for (Graph<T>::Edge e : this->edge[j])

                {

                    if (distance[e.to] > distance[j] + e.distance)

                    {

                        distance[e.to] = distance[j] + e.distance;

                    }

                }

            }

        }

        return distance;

    }



    // O(E + VlogV)

    // CAUTION: Use edge vector

    // CAUTION: Node-indices must be [1, N]

    vector<T> run_dijkstra(const long long from) const

    {

        vector<T> distance(this->node, this->initial_value);

        priority_queue<Graph<T>::Edge, vector<Graph<T>::Edge>, greater<Graph<T>::Edge>> queue;

        queue.push(Graph<T>::Edge(from, 0));

        for (long long i = 1; i < this->node && !queue.empty(); i++)

        {

            T d = queue.top().distance;

            long long to = queue.top().to;

            queue.pop();

            if (distance[to] == this->initial_value)

            {

                distance[to] = d;

                for (Graph<T>::Edge e : this->edge[to])

                {

                    if (distance[e.to] == this->initial_value)

                    {

                        queue.push({e.to, e.distance + d});

                    }

                }

            }

            else

            {

                i--;

            }

        }

        return distance;

    }



    // O(ElogV)

    // CAUTION: Use edge vector

    // CAUTION: Node-indices must be [1, N]

    T run_prim() const

    {

        vector<bool> is_visited(this->node, false);

        T cost = 0;

        priority_queue<Graph<T>::Edge, vector<Graph<T>::Edge>, greater<Graph<T>::Edge>> queue;

        queue.push(Graph<T>::Edge(1, 0));

        for (long long i = 1; i < this->node && !queue.empty(); i++)

        {

            T distance = queue.top().distance;

            long long to = queue.top().to;

            queue.pop();

            if (is_visited[to])

            {

                i--;

            }

            else

            {

                cost += distance;

                is_visited[to] = true;

                for (Graph<T>::Edge e : this->edge[to])

                {

                    queue.push({e.to, e.distance});

                }

            }

        }

        return cost;

    }



    // O(ElogV)

    // CAUTION: Use edge vector

    T run_kruskal() const

    {

        T cost = 0;

        vector<pair<Graph<T>::Edge, long long>> edge_from;

        for (long long i = 0; i < this->node; i++)

        {

            for (auto e : this->edge[i])

            {

                edge_from.push_back(make_pair(e, i));

            }

        }

        sort(edge_from.begin(), edge_from.end());



        Graph<T>::UnionFind uf(this->node);

        for (pair<Graph<T>::Edge, long long> e_f : edge_from)

        {

            auto e = e_f.first;

            long long from = e_f.second;

            if (!uf.has_same_root(from, e.to))

            {

                uf.unite(from, e.to);

                cost += e.distance;

            }

        }

        return cost;

    }



    // O(V)

    // CAUTION: Without cycle only

    // CAUTION: Use edge vector

    vector<long long> run_toporogical_sort() const

    {

        list<long long> ret_list;

        vector<bool> visited(this->node, false);

        for (long long i = 0; i < this->node; i++)

        {

            _dfs_toporogical_sort(visited, i, ret_list);

        }



        vector<long long> ret(ret_list.begin(), ret_list.end());

        return ret;

    }

};



int main()

{

    constexpr long long MAX_SILVER = 3000;

    size_t N, M;

    long long S;

    cin >> N >> M >> S;

    S = min(S, MAX_SILVER);



    Graph<pair<long long, long long>> g(N);

    long long U, V, A, B;

    for (size_t i = 0; i < M; i++)

    {

        cin >> U >> V >> A >> B;

        g.add_edge(U, V, make_pair(-A, B));

        g.add_edge(V, U, make_pair(-A, B));

    }



    long long C, D;

    for (size_t i = 1; i <= N; i++)

    {

        cin >> C >> D;

        g.add_edge(i, i, make_pair(C, D));

    }



    long long init = -1;

    vector<vector<long long>> d(N + 1, vector<long long>((size_t)MAX_SILVER + 1, init));

    priority_queue<pair<long long, pair<long long, long long>>, vector<pair<long long, pair<long long, long long>>>, greater<pair<long long, pair<long long, long long>>>> q;

    q.push(make_pair(0, make_pair(1, S)));

    for (size_t i = 0; i < (size_t)(N * M * MAX_SILVER) && !q.empty(); i++)

    {

        long long distance = q.top().first;

        long long to = q.top().second.first;

        long long silver = q.top().second.second;

        q.pop();



        if (d[to][silver] == init)

        {

            d[to][silver] = distance;



            for (auto e : g.edge[to])

            {

                long long next_silver = silver + e.distance.first;

                long long next_distance = distance + e.distance.second;

                if (next_silver < 0)

                {

                    continue;

                }

                next_silver = min(next_silver, MAX_SILVER);

                q.push(make_pair(next_distance, make_pair(e.to, next_silver)));

            }

        }

    }

    for (size_t i = 2; i <= N; i++)

    {

        long long ans = LONG_LONG_MAX;

        for (long long a : d[i])

        {

            if (a == init)

            {

                continue;

            }

            ans = min(ans, a);

        }

        cout << ans << endl;

    }

}


// Fastest known solution for this problem: