# Original solution
from heapq import heappush, heappop
import sys
n, m, s = map(int, input().split())
edges = list()
for _ in range(m):
  new_u, new_v, new_a, new_b = map(int, input().split())
  edges.append((new_u-1, new_v-1, new_a, new_b))
coins_range = (n-1)*max(edges,key=lambda item:item[2])[2]+1
c, d = list(), list()
for _ in range(n):
  new_c, new_d = map(int, input().split())
  c.append(new_c)
  d.append(new_d)
adjacency = {(i, j): [] for i in range(n) for j in range(coins_range)}
for (node, coins) in adjacency.keys():
  new_coins = coins+c[node]
  if new_coins<=coins_range-1:
    adjacency[(node, coins)].append(((node, coins+c[node]), (d[node])))
for edge in edges:
  node1, node2, cost, weight = edge
  for coins in range(cost, coins_range):
    adjacency[(node1, coins)].append(((node2, coins-cost), weight))
    adjacency[(node2, coins)].append(((node1, coins-cost), weight))
def dijkstra():
  while state_heap:
    distance, state = heappop(state_heap)
    visited[state] = True
    for (new_state, weight) in adjacency[state]:
      if not visited[new_state]:
        distances[new_state] = min(distances[new_state], distance+weight)
        heappush(state_heap, (distances[new_state], new_state))
distances = {(i, j): float("inf") for i in range(n) for j in range(coins_range)}
initial_state = (0, min(s, coins_range-1))
distances[initial_state] = 0
state_heap = []
heappush(state_heap, (distances[initial_state], initial_state))
visited = {(i, j): False for i in range(n) for j in range(coins_range)}
visited[initial_state] = True
dijkstra()
final_distances = [float("inf")]*n
for ((node, _), distance) in distances.items():
  final_distances[node] = min(final_distances[node], distance)
[print(distance) for distance in final_distances[1:]]


# Optimized solution
from heapq import heappush, heappop
import sys
n, m, s = map(int, input().split())
edges = list()
for _ in range(m):
  new_u, new_v, new_a, new_b = map(int, input().split())
  edges.append((new_u-1, new_v-1, new_a, new_b))
coins_range = (n-1)*max(edges,key=lambda item:item[2])[2]+1
c, d = list(), list()
for _ in range(n):
  new_c, new_d = map(int, input().split())
  c.append(new_c)
  d.append(new_d)
adjacency = {(i, j): [] for i in range(n) for j in range(coins_range)}
for (node, coins) in adjacency.keys():
  new_coins = coins+c[node]
  if new_coins<=coins_range-1:
    adjacency[(node, coins)].append(((node, coins+c[node]), (d[node])))
for edge in edges:
  node1, node2, cost, weight = edge
  for coins in range(cost, coins_range):
    adjacency[(node1, coins)].append(((node2, coins-cost), weight))
    adjacency[(node2, coins)].append(((node1, coins-cost), weight))
def dijkstra():
  while state_heap:
    distance, state = heappop(state_heap)
    if visited[state]:
      continue
    visited[state] = True
    for (new_state, weight) in adjacency[state]:
      if not visited[new_state]:
        distances[new_state] = min(distances[new_state], distance+weight)
        heappush(state_heap, (distances[new_state], new_state))
distances = {(i, j): float("inf") for i in range(n) for j in range(coins_range)}
initial_state = (0, min(s, coins_range-1))
distances[initial_state] = 0
state_heap = []
heappush(state_heap, (distances[initial_state], initial_state))
visited = {(i, j): False for i in range(n) for j in range(coins_range)}
dijkstra()
final_distances = [float("inf")]*n
for ((node, _), distance) in distances.items():
  final_distances[node] = min(final_distances[node], distance)
[print(distance) for distance in final_distances[1:]]