class Station
  attr_accessor :mins, :rails
  def initialize(num)
    @number = num
    @rails = []
    @mins = [Array.new(@@m, 10 ** 6), Array.new(@@m, 10 ** 6)]
  end

  def self.set_n(m)
    @@m = m + 1
    @@stations = Array.new(m + 1){|i|Station.new(i)}
  end

  def self.set_rail(a, b, cost, time)
    @@stations[a].rails << [@@stations[b], cost, time]
    @@stations[b].rails << [@@stations[a], cost, time]
  end

  def self.setup
    (1...@@m).each do |i|
      2.times do |r|
        @@stations[i].mins[r][i] = 0
        (1...i).each do |j|
          @@stations[j].mins[r][i] = @@stations[i].mins[r][j]
        end
        cal(i, r)
      end
    end
  end
  
  def self.cal(n, r)
    stack = @@stations.dup.sort_by{|f|f.mins[r][n]}
    while (st = stack.shift)
      st.ride(n, r)
      stack.sort_by!{|f|f.mins[r][n]}
    end
  end

  def inspect
    return @number
  end

  def to_s
    inspect
  end

  def ride(n, f)
    @rails.each{|r|r[0].mins[f][n] = mins[f][n] + r[f + 1] if (r[0].mins[f][n] > mins[f][n] + r[f + 1])}
  end

  def self.min(a, b, r)
    return @@stations[a].mins[r][b]
  end
   
end

def main(input = STDIN)
  n, m = input.gets.split(" ").map(&:to_i)
  Station.set_n(m)
  n.times do
    Station.set_rail(*input.gets.split(" ").map(&:to_i))
  end
  Station.setup
  input.gets.to_i.times do
    puts Station.min(*input.gets.split(" ").map(&:to_i))
  end
end
main