#!/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

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_used(time, left)
    @gas_filled = time
    @gas_left = left
#    $stderr.puts "#{@city.a}: filled #{@gas_filled}, left #{@gas_left}"
    self
  end
  def gas_need(time, least)
    @gas_filling = time
    @gas_least = least
#    $stderr.puts "#{@city.a}: need filling #{@gas_filling}, more #{@gas_least}"
    self
  end
  attr_reader :city, :gas_filled, :gas_left, :gas_filling, :gas_least
  def inspect
    "#{@city.a}: gas #{@gas_filled} times and #{@gas_left} litter left from S, #{@gas_filling} time and #{@gas_least} litter necessary to T"
  end
  def to_s
    inspect
  end
end

_, 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

#$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_used(0, l)]
  to = [Reach.reach(City.city(t)).gas_need(0, 0)]
  while from.size > 0
    # スタートからゴールに向けて
#    $stderr.puts "from = #{from}"
#    $stderr.puts "to = #{to}"
    a = from.shift
    if a.gas_filling != nil
      # t へのルートが見えたら、それでいいかも
#      $stderr.puts "time = #{a.gas_filled} + #{a.gas_filling}"
      time = a.gas_filled + a.gas_filling
      if a.gas_left < a.gas_least
        time += 1
      end
      if gt < 0 || gt > time
        gt = time
      end
    else
      # a の次ホップとそこまでに消費したガスを求める
      a.city.road.each do |r|
        # b とそこまでのガス消費量を求める
        b = Reach.reach(City.city(r.d).a)
        if a.gas_left < r.c
          time = a.gas_filled + 1
          left = l - r.c
        else
          time = a.gas_filled
          left = a.gas_left - r.c
        end
        # それが b への最短っぽそうだったら、b の先を探すようにする
        if b.gas_filled == nil || time < b.gas_filled || (time == b.gas_filled && left > b.gas_left)
          b.gas_used(time, left)
          idx = from.bsearch_index {|x| x.gas_filled > time || (x.gas_filled == time && x.gas_left < left)}
          if idx == nil
            from.push(b)
          else
            from.insert(idx, b)
          end
        end
      end
    end
    # ゴールからスタートに戻って
#    $stderr.puts "from = #{from}"
#    $stderr.puts "to = #{to}"
    b = to.shift
    if b.gas_filled != nil
      # s へのルートがみえたら、それでいいかも
#      $stderr.puts "time = #{b.gas_filling} + #{b.gas_filled}"
      time = b.gas_filling + b.gas_filled
      if b.gas_left < b.gas_least
        time += 1
      end
      if gt < 0 || gt > time
        gt = time
      end
    else
      # b の前ホップとそこから必要なガスを求める
      b.city.road.each do |r|
        # a とそこから必要なガス消費量を求める
        a = Reach.reach(City.city(r.d).a)
        if b.gas_least + r.c <= l
          time = b.gas_filling
          least = b.gas_least + r.c
        else
          time = b.gas_filling + 1
          least = r.c
        end
        # それが a からの最短っぽそうだったら、a の先を探すようにする
        if a.gas_filling == nil || time < a.gas_filling || (time == a.gas_filling && least < a.gas_least)
          a.gas_need(time, least)
          idx = to.bsearch_index {|x| x.gas_filling > time || (x.gas_filling == time && x.gas_least> least)}
          if idx == nil
            to.push(a)
          else
            to.insert(idx, a)
          end
        end
      end
    end
    if gt >= 0
      break
    end
  end

  puts gt
end
