### BUGGY CODE ###

import heapq
N, M, S = map(int, input().split())
G = [[] for _ in range(N)]
for i in range(M):
    u, v, a, b = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, a, b])
    G[v].append([u, a, b])

C, D = [], []
for i in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)


S = min(2500, S)
# dp[node][silver] := 頂点nodeにいてsilver枚の銀貨を持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * 2501 for _ in range(N)]
distances = [float('inf')] * N
distances[0] = 0
hq = []  # これまでにかかった時間がtimeで、silver枚銀貨を持っていて、頂点nodeにいる

# 頂点0について全両替バターンを試しておく
produce_silver_profit = C[0]
produce_silver_cost = D[0]
push_silver = S + produce_silver_profit
push_time = 0 + produce_silver_cost

heapq.heappush(hq, (0, S, 0))
while push_silver <= 2500:
    dp[0][push_silver] = min(dp[0][push_silver], push_time)
    heapq.heappush(hq, (push_time, push_silver, 0))
    push_silver += produce_silver_profit
    push_time += produce_silver_cost

while hq:
    time, silver, node = heapq.heappop(hq)
    for to, cost_silver, cost_time in G[node]:
        if silver < cost_silver:
            continue

        new_time = time + cost_time
        distances[to] = min(distances[to], new_time)

        produce_silver_profit = C[to]
        produce_silver_cost = D[to]

        push_silver = silver - cost_silver
        push_time = new_time
        if dp[to][max(0, min(2500, push_silver))] <= push_time:
            push_silver += produce_silver_profit
            push_time += produce_silver_cost
            continue

        heapq.heappush(hq, (push_time, push_silver, to))
        while push_silver <= 2500:
            if dp[to][push_silver] <= push_time:
                push_silver += produce_silver_profit
                push_time += produce_silver_cost
                continue

            dp[to][push_silver] = push_time
            heapq.heappush(hq, (push_time, push_silver, to))
            push_silver += produce_silver_profit
            push_time += produce_silver_cost

print(*distances[1:], sep="\n")


### FIXED CODE ###

import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    change_rate.append(rate)
    change_cost.append(cost)


# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    self_loop_silver = min(silver + change_rate[node], MAX_COST)
    self_loop_cost = time + change_cost[node]
    if self_loop_cost < dp[node][self_loop_silver]:
        dp[node][self_loop_silver] = self_loop_cost
        heapq.heappush(hq, (time + change_cost[node], node, self_loop_silver))

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] <= dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")