Infinity = 1.0 / 0.0
class Station
  attr_reader :m, :cost
  def initialize(m)
    @m = m
    @rails = []
    @r = nil
    @cost = Infinity
  end
  def ==(other)
    @m == other
  end
  def start
    @cost = 0
  end
  def setup(r)
    @r = r
    @cost = Infinity
  end
  def set_r(b, cost, time)
    @rails << [b, cost, time]
  end
  def ride
    @rails.each{|rail|
      rail[0].reach(@cost + rail[@r + 1])
    }
  end
  def reach(cost)
    @cost = cost if @cost > cost
  end
end
class Chain
  def initialize(args, r)
    @s = S_ring.new
    @l = L_ring.new
    @s.ne = @l
    args.each{|f|
      f.setup(r)
      @s.push(Ring.new(f))
    }
  end
  def get
    return @s.min.chomp
  end
end
class S_ring
  attr_accessor :ne
  def initialize
    @ne = nil
  end
  def min
    @ne.min(@ne)
  end
  def push(ring)
    ring.ne = @ne
    @ne.pr = ring
    ring.pr = self
    @ne = ring
  end
end
class L_ring
  attr_accessor :pr
  def initialize
    @pr = nil
  end
  def min(minv)
    return minv
  end
end
class Ring
  include Comparable
  attr_accessor :factor, :pr, :ne
  def initialize(factor)
    @factor = factor
    @pr = nil
    @ne = nil
  end
  def <=>(other)
    @factor.cost <=> other.factor.cost
  end
  def min(minv)
    return @ne.min((minv > self)? self : minv)
  end
  def chomp
    @pr.ne = @ne
    @ne.pr = @pr
    return @factor
  end
end
def main(input = STDIN)
  while (n, m = input.gets.split(" ").map(&:to_i)) != [0, 0]
    st = Array.new(m){|i|Station.new(i + 1)}
    n.times do
      rail = input.gets.split(" ").map(&:to_i)
      st[rail[0] - 1].set_r(st[rail[1] - 1], *rail[2,2])
      st[rail[1] - 1].set_r(st[rail[0] - 1], *rail[2,2])
    end
    input.gets.to_i.times do
      request = input.gets.split(" ").map(&:to_i)
      chain = Chain.new(st, request[2])
      st[request[0] - 1].start
      while (min = chain.get) != request[1]
        min.ride
      end
      puts min.cost
    end
  end
end
main