class Graph
  attr_reader :nodes
  
  def initialize(n)
    @n = n
    @nodes = Array.new(@n) { [] }
  end
  
  def add(from, to, cost, time)
    @nodes[from] << [from, to, cost, time]
    @nodes[to] << [to, from, cost, time]
  end
  
  def size
    @n
  end
end

def dijekstra(start, graph, value_as_dist)
  n = graph.size
  dist = Array.new(n) { Float::INFINITY }
  is_fixed = Array.new(n) { false }
  queue = [*0...n]
  
  dist[start] = 0
  is_fixed[start] = true
  
  until queue.empty?
    queue.sort_by! { |i| dist[i] }
    
    tmp = queue.shift
    is_fixed[tmp] = true
    
    graph.nodes[tmp].each do |from, to, cost, time|
      next if is_fixed[to]
      new_len = dist[from] + (value_as_dist == 0 ? cost : time)
      
      if new_len < dist[to]
        dist[to] = new_len
      end
    end
  end
  
  dist
end

while true
  n, m = gets.split.map(&:to_i)

  break if n + m == 0

  graph = Graph.new(m)
  memo = Array.new(m) { Array.new(2) }

  n.times do
    a, b, cost, time = gets.split.map(&:to_i)
    
    graph.add(a - 1, b - 1, cost, time)
  end
  
  gets.to_i.times do
    p_k, q_k, r_k = gets.split.map(&:to_i)

    memo[p_k - 1][r_k + 1] = dijekstra(p_k - 1, graph, r_k) if memo[p_k - 1][r_k + 1].nil?
    
    puts memo[p_k - 1][r_k + 1][q_k - 1]
  end
end