class Station
  attr_reader :id
  attr_accessor :cost
  def initialize(id)
    @id = id
    @rail = []
    @cost = nil
  end

  def set_rail(rail)
    @rail << rail
  end

  def next_s(type, min)
    if @cost and min.cost > @cost.cost
      []
    else
      @cost = min
      temp = @rail.select{|item|item.cut(self, min, type)}.map{|item|item.ride(self, min, type)}.select{|item|!item.s.cost or item.s.cost > item}
      temp.each{|item|min << item}
      return temp    
    end
    
  end

  def ==(other)
    @id == other.id
  end

  def inspect
    return "Station #{@id}-#{@cost.to_s}-rail.size#{@rail.size}"
  end
  
end

class Stations
  def initialize(m)
    @stations = Array.new(m){|i|Station.new(i + 1)}
    def @stations.[](n)
      super(n - 1)
    end
    def @stations.[]=(n, other)
      super(n - 1, other)
    end
    @rails = []
  end

  def set_rail(str)
    str = str.split(" ").map(&:to_i)
    @rails << Rail.new(@stations[str[0]], @stations[str[1]], str[2], str[3])
    @stations[str[0]].set_rail(@rails[-1])
    @stations[str[1]].set_rail(@rails[-1])
  end

  def search(a, b, type)
    #p [a,b,type]                # => [1, 5, 0], [1, 5, 1]
    costs = Array.new(@stations.size)
    def costs.[](n)
      super(n - 1)
    end
    def costs.[]=(n, other)
      if !self[n] or self[n] > other
        super(n - 1, other)
      end
    end
    def costs.replace(args)
      #p args                    
      args.each do |item|
        self[item.s.id] = item
      end
    end
    costs[a] = Cost.new(@stations[a], 0)
    min = costs[a]              # => Cost-Station1-0, Cost-Station1-0
    while !costs[b] or costs[b] != min
      #p min
      costs.replace(min.s.next_s(type, min))
      #p costs
      min = min.delete.min
      #p min                     # => Cost-Station2-200, Cost-Station3-250, Cost-Station4-300, Cost-Station4-400, Cost-Station5-450, Cost-Station2-10, Cost-Station4-15, Cost-Station4-20, Cost-Station3-25, Cost-Station5-35
    end
    puts costs[b].cost
  end
  def inspect
    return "Group of Stations"
  end
    
end
class Cost
  include Comparable
  attr_reader :cost, :s
  attr_accessor :smaller, :bigger
  def initialize(station, cost)
    #p [station, cost]
    @s = station                #
    @cost = cost
    @smaller = nil
    @bigger = nil
  end

  def inspect
    return "Cost-Station#{@s.id}-#{@cost}"
  end

  def to_s
    return @cost
  end

  def to_exp
    max.expression
  end

  def expression
    if @smaller
      return @smaller.expression + " << Sta#{@s.id}-Cos#{@cost}"
    else
      return "Sta#{@s.id}-Cos#{@cost}"
    end
  end

  def <<(other)
    if self > other
      if @smaller
        small = self
        while (small = small.smaller) and (small > other)
          temp = small
        end
        #p [temp.to_exp, other.inspect] # => 
        temp.smaller = other
        other.bigger = temp
        small.bigger, other.smaller = other, small if small
        #p temp.to_exp           # => 
      else
        @smaller = other
        other.bigger = self
        #p self.to_exp           # => 
      end
    else
      if @bigger
        big = self
        while (big = big.bigger) and (big < other)
          temp = big
        end
        #p [temp.to_exp, other.inspect]
        temp.bigger = other
        other.smaller = temp
        big.smaller, other.bigger = other, big if big
        #p temp.to_exp           # => "Sta1-Cos0 << Sta2-Cos200 << Sta4-Cos400", "Sta1-Cos0 << Sta2-Cos200 << Sta3-Cos250 << Sta4-Cos400", "Sta2-Cos200 << Sta3-Cos250 << Sta4-Cos300 << Sta4-Cos400", "Sta3-Cos250 << Sta4-Cos300 << Sta4-Cos400 << Sta5-Cos550", "Sta4-Cos300 << Sta4-Cos400 << Sta5-Cos450 << Sta5-Cos550", "Sta1-Cos0 << Sta2-Cos10 << Sta4-Cos15", "Sta1-Cos0 << Sta2-Cos10 << Sta4-Cos15 << Sta3-Cos25", "Sta2-Cos10 << Sta4-Cos15 << Sta4-Cos20 << Sta3-Cos25", "Sta4-Cos15 << Sta4-Cos20 << Sta3-Cos25 << Sta5-Cos35", "Sta3-Cos25 << Sta5-Cos35 << Sta5-Cos45"
      else
        @bigger = other
        other.smaller = self
        #p self.to_exp           # => "Sta1-Cos0 << Sta2-Cos200", "Sta1-Cos0 << Sta2-Cos10"
      end
    end
    return self
  end

  def min
    suspect = self
    while suspect.smaller
      suspect = suspect.smaller
    end
    return suspect
  end

  def max
    suspect = self
    while suspect.bigger
      suspect = suspect.bigger
    end
    return suspect
  end

  def <=>(other)
    @cost <=> other.cost
  end

  def delete
    @bigger.smaller = @smaller if @bigger
    @smaller.bigger = @bigger if @smaller
    return @bigger
  end
  
end

class Rail
  def initialize(a, b,cost, time)
    @cost = [cost, time]
    @a = a
    @b = b
  end

  def ride(start, cost, type)
    if start == @a
      return Cost.new(@b, @cost[type] + cost.cost)
    else
      return Cost.new(@a, @cost[type] + cost.cost)
    end
  end

  def inspect
    return "Rail-from #{@a.id}-to #{@b.id}"
  end

  def cut(start, cost, type)
    if start == @a
      return (!@b.cost or (@b.cost.cost > (cost.cost + @cost[type])))
    else
      return (!@a.cost or (@a.cost.cost > (cost.cost + @cost[type])))
    end
  end
  
end

def main
  while (n, m = gets.split(" ").map(&:to_i)) != [0, 0]
    stations = Stations.new(m)
    n.times do
      stations.set_rail(gets.chomp)
    end
    #p "start search"            # => "start search"
    gets.to_i.times do
      stations.search(*gets.split(" ").map(&:to_i))
    end
  end

end

main