program main
  implicit none
  integer(8) :: n, m, s, i, rep
  integer(8), allocatable :: a(:), b(:), u(:), v(:), c(:), d(:), dp(:, :)
  read *, n, m, s
  allocate (a(m), b(m), u(m), v(m), c(n), d(n), dp(0:5000, n))
  do i = 1, m
    read *, u(i), v(i), a(i), b(i)
  end do
  do i = 1, n
    read *, c(i), d(i)
  end do
  dp = 10_8 ** 18
  dp(min(5000_8, s), 1) = 0
  call update_city(1_8)
  do rep = 1, n * 2
    do i = 1, m
      call move(i)
      call update_city(u(i))
      call update_city(v(i))
    end do
  end do
  do i = 2, n
    print "(i0)", dp(0, i)
  end do

  contains
  subroutine update_city(city)
    ! cityでの両替によりdp(:, city)を更新する
    integer(8), intent(in) :: city
    integer(8) :: i
    do i = 1, 5000  ! もらう
      if (i - c(city) >= 0) then
        dp(i, city) = min(dp(i, city), dp(i - c(city), city) + d(city))
      end if
    end do
    do i = 4999, 0, -1
      dp(i, city) = min(dp(i, city), dp(i + 1, city))
    end do
  end subroutine update_city

  subroutine move(edge)
    ! edge(city1-city2)の移動を評価することにより、dp(:, city[12])を更新する
    integer(8), intent(in) :: edge
    integer(8) :: from, to
    from = u(edge)
    to = v(edge)
    dp(0:5000 - a(edge), to) = min(dp(0:5000 - a(edge), to), dp(a(edge):5000, from) + b(edge))
    from = v(edge)
    to = u(edge)
    dp(0:5000 - a(edge), to) = min(dp(0:5000 - a(edge), to), dp(a(edge):5000, from) + b(edge))
  end subroutine move
end program main
