#!/usr/bin/env ruby
# coding: utf-8

class City
  @@db = Hash.new {|h,k| h[k] = City.new(k)}
  def self.db
    @@db
  end
  def self.city(x)
    @@db[x]
  end
  def initialize(a)
    @a = a
    @road = []
  end
  attr_reader :a, :road
  def inspect
    "#{@road}"
  end
end

class Road
  def self.create(a, b, c)
    a = City.city(a)
    b = City.city(b)
    ab = Road.new(c, b)
    ba = Road.new(c, a)
    a.road.push(ab)
    b.road.push(ba)
  end

  def initialize(c, d)
    @c = c
    @d = d
  end
  attr_reader :c, :d
  def inspect
    "#{@c} => #{@d.a}"
  end
end

n, m, l = ARGF.gets.split.map(&:to_i)

m.times do
  a, b, c = ARGF.gets.split.map(&:to_i)
  Road.create(a, b, c)
end

class Reach
  def self.init
    @@db = Hash.new {|hash,key| hash[key] = Reach.new(key)}
  end
  def self.db
    @@db
  end
  def self.reach(key)
    @@db[key]
  end
  def initialize(city)
    @city = city
  end
  def gas(time, left)
    @gas_time = time
    @gas_left = left
    self
  end
  attr_reader :city, :gas_time, :gas_left
  def inspect
    "#{@city.a}: gas #{@gas_time} times and #{@gas_left} litter left"
  end
  def to_s
    inspect
  end
end

#$stderr.puts "#{City.db}"

ARGF.gets.to_i.times do
  Reach.init
  s, t = ARGF.gets.split.map(&:to_i)
  gt = -1
  # スタートからゴールに向けて
  from = [Reach.reach(City.city(s)).gas(0, l)]
  while a = from.shift
    #$stderr.puts "#{a}, #{from}"
    if a.city.a == t
      gt = a.gas_time
      break
    end
    a.city.road.each do |r|
      b = Reach.reach(City.city(r.d).a)
      if a.gas_left < r.c
        time = a.gas_time + 1
        left = l - r.c
      else
        time = a.gas_time
        left = a.gas_left - r.c
      end
      next if b.gas_time && b.gas_time < time
      next if b.gas_time == time && b.gas_left < left
      b.gas(time, left)
      ins = from.bsearch_index {|x| x.gas_time > time || (x.gas_time == time && x.gas_left > left)}
      if ins == nil
        from.push(b)
      else
        from.insert(ins, b)
      end
    end
  end
  puts gt
end
