module mod_graph
  implicit none
  integer(8), parameter :: inf = 10000000
  type item
    integer :: id = 0
    integer(8) :: wt = 0_8
  end type
  type priorityqueue
    integer :: num = 0
    type(item), pointer :: heap(:) => null()
  end type
  type edge
    integer :: fm = 0, to = 0, cp = 0, rv = 0
    integer(8) :: wt = 0_8
  end type
  type arraylist
    integer :: num = 0
    type(edge), pointer :: arr(:) => null()
  contains
    procedure :: add => adde
  end type
  type graph
    type(arraylist), pointer :: egs(:) => null()
    logical, pointer :: used(:) => null()
  contains
    procedure :: add => add
  end type
  interface graph
    module procedure :: newg
  end interface graph
contains
  function newi(id,wt) result(ret)
    integer, intent(in) :: id
    integer(8), intent(in) :: wt
    type(item) :: ret
    ret%id = id
    ret%wt = wt
  end
  subroutine swapi(a,b)
    type(item), intent(inout) :: a, b
    type(item) :: c
    c = a
    a = b
    b = c
  end
  subroutine appendi(a)
    type(item), pointer, intent(inout) :: a(:)
    integer :: n
    type(item), allocatable :: tmp(:)
    n = size(a)
    allocate(tmp(n))
    tmp = a
    deallocate(a)
    allocate(a(2*n))
    a(1:n) = tmp
    deallocate(tmp)
  end
  function lessi(a,b) result(ret)
    type(item), intent(in) :: a, b
    logical :: ret
    ret = a%wt < b%wt
  end
  subroutine offer(pq,it)
    type(priorityqueue), intent(inout) :: pq
    type(item), intent(in) :: it
    integer :: i, j
    if (.not.associated(pq%heap)) allocate(pq%heap(1))
    if (pq%num == size(pq%heap)) call appendi(pq%heap)
    pq%num = pq%num+1
    pq%heap(pq%num) = it
    i = pq%num
    do while (i > 1)
      j = i/2
      if (lessi(pq%heap(i),pq%heap(j))) call swapi(pq%heap(i),pq%heap(j))
      i = j
    end do
  end
  function poll(pq) result(ret)
    type(priorityqueue), intent(inout) :: pq
    type(item) :: ret
    integer :: n, i, j
    n = pq%num
    ret = pq%heap(1)
    pq%heap(1) = pq%heap(n)
    pq%num = pq%num-1
    i = 1
    do while (2*i < n)
      j = 2*i
      if (j+1 < n .and. lessi(pq%heap(j+1),pq%heap(j))) j = j+1
      if (lessi(pq%heap(j),pq%heap(i))) call swapi(pq%heap(j),pq%heap(i))
      i = j
    end do
  end
  function newe(to,wt,fm,cp,rv) result(ret)
    integer, intent(in) :: to
    integer(8), intent(in) :: wt
    integer, intent(in), optional :: fm, cp, rv
    type(edge) :: ret
    if (present(fm)) ret%fm = fm
    ret%to = to
    ret%wt = wt
    if (present(cp) .and. present(rv)) then
      ret%cp = cp
      ret%rv = rv
    end if
  end
  subroutine appende(a)
    type(edge), pointer, intent(inout) :: a(:)
    integer :: n
    type(edge), allocatable :: tmp(:)
    n = size(a)
    allocate(tmp(n))
    tmp = a
    deallocate(a)
    allocate(a(2*n))
    a(1:n) = tmp
    deallocate(tmp)
  end
  function lesse(a,b) result(ret)
    type(edge), intent(in) :: a, b
    logical :: ret
    ret = a%wt < b%wt
  end
  subroutine adde(list,e)
    class(arraylist), intent(inout) :: list
    type(edge), intent(in) :: e
    if (.not.associated(list%arr)) allocate(list%arr(1))
    if (list%num == size(list%arr)) call appende(list%arr)
    list%num = list%num+1
    list%arr(list%num) = e
  end
  function newg(n) result(ret)
    integer, intent(in) :: n
    type(graph) :: ret
    allocate(ret%egs(n))
  end
  subroutine add(g,fm,to,wt,cp)
    class(graph), intent(inout) :: g
    integer, intent(in) :: fm, to
    integer, intent(in), optional :: cp
    integer(8) :: wt
    if (present(cp)) then
      call adde(g%egs(fm),newe(to,wt,cp=cp,rv=g%egs(to)%num))
      call adde(g%egs(to),newe(fm,wt,cp=0,rv=g%egs(fm)%num-1))
    else
      call adde(g%egs(fm),newe(to,wt))
    end if
  end
end module mod_graph
program travel_by_car
  use mod_graph
  implicit none
  integer :: n, m, a, b, q, s, t, i, j
  integer(8) :: l, c
  integer :: x(300,300) = inf
  type(graph) :: g
  read(*,*) n, m, l
  g = graph(n)
  do i = 1, n
    call g%add(i,i,0_8)
  end do
  do i = 1, m
    read(*,*) a, b, c
    call g%add(a,b,c)
    call g%add(b,a,c)
  end do
  do i = 1, n
    call dfs(i,i,l,0)
  end do
  read(*,*) q
  do i = 1, q
    read(*,*) s, t
    if (x(s,t) == inf) then
      write(*,'(i0)') -1
    else
      write(*,'(i0)') x(s,t)
    end if
  end do
contains
  recursive subroutine dfs(s,u,gas,m)
    integer, intent(in) :: s, u, m
    integer(8), intent(in) :: gas
    integer :: v, i
    integer(8) :: c
    if (x(s,u) <= m) return
    x(s,u) = m
    do i = 1, g%egs(u)%num
      v = g%egs(u)%arr(i)%to
      c = g%egs(u)%arr(i)%wt
      if (gas >= c) then
        call dfs(s,v,gas-c,m)
      else if (l >= c) then
        call dfs(s,v,l-c,m+1)
      end if
    end do
  end
end program travel_by_car