#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
#include <unordered_map>
#include <cstring>
#include <algorithm>
#include <set>
#include <climits>
#include <numeric>

//usings
using namespace std;

//type def
typedef long long int64;
typedef pair<int, int> ii;

//consts
const int mod = 1e9 + 7;
const int coin_limit = 2500;

//methods
template<typename T> bool chmax(T& source, const T& compare_to) { if(source < compare_to) { source = compare_to; return true;} return false; }
template<typename T> bool chmin(T& source, const T& compare_to) { if(source > compare_to) { source = compare_to; return true;} return false; }

int modpow(int64 base, int n) {
    int64 ret = 1;
    while(n) {
        if(n & 1) ret = ret * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return ret;
}
struct Edge {
    int to, cost, trav_time;
    Edge(int to, int cost, int time) : to(to), cost(cost), trav_time(time) {}
};

struct Node
{
    int64 time;
    int vertex, coins;
    Node(int64 time, int vertex, int coins) : time(time), vertex(vertex), coins(coins) {}

    bool operator> (const Node& to) const{
        return this->time > to.time;
    }
};

class Solution {
private:
public:
    vector<int64> solve(int n, int start_coin, vector<vector<Edge>>& graph, vector<int>& exchange_rate, vector<int>& exchange_time) {
        vector<vector<int64>> dp(n + 1, vector<int64>(coin_limit + 1, INT64_MAX));
        start_coin = min(start_coin, coin_limit);
        dp[1][start_coin] = 0; //start node is 0 cost
        priority_queue<Node, vector<Node>, greater<Node>> pq;
        pq.push(Node(0, 1, start_coin));
        while(!pq.empty()) {
            auto node = pq.top();
            pq.pop();
            if(node.time > dp[node.vertex][node.coins]) continue;
            //exchange
            if(node.coins + exchange_rate[node.vertex] <= coin_limit) {
                int new_coin = node.coins + exchange_rate[node.vertex];
                int64 new_time = node.time + exchange_time[node.vertex];
                if(chmin(dp[node.vertex][new_coin], new_time)) {
                    pq.push(Node(new_time, node.vertex, new_coin));
                }
            }
            //try to pass every vector
            for(const auto& next : graph[node.vertex]) {
                if(node.coins < next.cost) continue; //not enough coin
                int new_coin = node.coins - next.cost;
                int64 new_time = node.time + next.trav_time;
                if(chmin(dp[next.to][new_coin], new_time)) {
                    pq.push(Node(new_time, next.to, new_coin));
                }
            }
        }
        vector<int64> ret(n - 1);
        for(int v = 2; v <= n; ++v) {
            int64 cur = INT64_MAX;
            for(int coins = 0; coins <= coin_limit; ++coins) chmin(cur, dp[v][coins]);
            ret[v - 2] = cur;
        }
        return ret;
    }
};

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<Edge>> graph(n + 1, vector<Edge>());
    for(int i = 0; i < m; ++i) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        graph[u].emplace_back(v, a, b);
        graph[v].emplace_back(u, a, b);
    }
    vector<int> exchange_rate(n + 1), exchange_time(n + 1);
    for(int i = 1; i <= n; ++i) {
        cin >> exchange_rate[i] >> exchange_time[i];
    }
    Solution sol;
    auto ret = sol.solve(n, s, graph, exchange_rate, exchange_time);
    for(const auto& r : ret) cout << r << endl;
}

Measured memory_bytes: 6372