local mmi, mma = math.min, math.max
local n, m, s = io.read("*n", "*n", "*n")
local edge = {}
for i = 1, n do
  edge[i] = {}
end
local line = {}
for i = 1, m do
  local u, v, a, b = io.read("*n", "*n", "*n", "*n")
  edge[u][v] = {a, b}
  edge[v][u] = {a, b}
  line[i] = {u, v, a, b}
end
local coin = {}
local changetime = {}
for i = 1, n do
  coin[i], changetime[i] = io.read("*n", "*n")
end
local dp = {}
for i = 1, n do
  dp[i] = {}
  for j = 1, 2501 do
    dp[i][j] = -1
  end
end
s = mmi(s, 2500)
dp[1][s + 1] = 0
local function updateCity()
  for i = 1, n do
    for j = 1, 2501 do
      if 0 <= dp[i][j] then
        local dst = mmi(2501, j + coin[i])
        if dp[i][dst] < 0 then
          dp[i][dst] = dp[i][j] + changetime[i]
        else
          dp[i][dst] = mmi(dp[i][dst], dp[i][j] + changetime[i])
        end
      end
    end
  end
end
local function moveOn()
  for il = 1, m do
    local u, v, a, b = unpack(line[il])
    for i = 1 + a, 2501 do
      if 0 <= dp[u][i] then
        if dp[v][i - a] < 0 then
          dp[v][i - a] = dp[u][i] + b
        else
          dp[v][i - a] = mmi(dp[v][i - a], dp[u][i] + b)
        end
      end
      if 0 <= dp[v][i] then
        if dp[u][i - a] < 0 then
          dp[u][i - a] = dp[v][i] + b
        else
          dp[u][i - a] = mmi(dp[u][i - a], dp[v][i] + b)
        end
      end
    end
  end
end
for i = 1, 111 do
  updateCity()
  moveOn()
end
for i = 2, n do
  local ret = -1
  for j = 1, 2501 do
    if 0 <= dp[i][j] then
      if ret < 0 then
        ret = dp[i][j]
      else
        ret = mmi(ret, dp[i][j])
      end
    end
  end
  print(ret)
end
