require 'set'

class Graph
  def initialize m, lines
    @station_h = {}
    lines.each {|(a_id, b_id, price, distance)|
      get_or_create_station(a_id)
        .link_with(get_or_create_station(b_id), price, distance)
    }
    # init memo
    @min_cost_memo = @station_h.values.each_with_object({}) {|start_station, memo|
      memo[start_station] = [0, 1].each_with_object({}) {|cost_type, part|
        part[cost_type] = {}
      }
    }
  end

  def get_or_create_station id
    @station_h[id] || @station_h[id] = Station.new(id)
  end

  def calc_min_cost start, goal, cost_type
    start_station = get_or_create_station start
    goal_station = get_or_create_station goal
    
    if @min_cost_memo[start_station][cost_type].empty?
      scan_all start_station, 0, Set.new(@station_h.values.reject {|s| s == start_station}), start_station, cost_type
    end
    @min_cost_memo[start_station][cost_type][goal_station]
  end

  def scan_all current_station, current_cost, remain_stations, start_station, cost_type
    current_min_cost = @min_cost_memo[start_station][cost_type][current_station]
    return if !current_min_cost.nil? && current_min_cost < current_cost 
    @min_cost_memo[start_station][cost_type][current_station] = current_cost
    current_station
      .links
      .select {|(s, _, _)| remain_stations.include? s }
      .each {|(s, c_0, c_1)|
        scan_all s, current_cost + [c_0, c_1][cost_type], remain_stations - [current_station], start_station, cost_type
      }
  end

  class Station
    attr_reader :id, :links

    def initialize id
      @id = id
      @links = []
    end

    def link_with target_station, price, distance
      links << [target_station, price, distance]
      target_station.links << [self, price, distance]
    end
  end
end

Enumerator.new {|y|
  until (n_m = gets.split(" ").map(&:to_i)) == [0, 0]
    n, m = *n_m
    lines = n.times.map { gets.split(" ").map(&:to_i) }
    issues = gets.to_i.times.map { gets.split(" ").map(&:to_i) }
    y << [m, lines, issues]
  end
}
  .flat_map {|(m, lines, issues)|
    g = Graph.new(m, lines)
    issues.map {|start, goal, cost_type|
      g.calc_min_cost start, goal, cost_type
    }
  }
  .each(&method(:puts))