#!/usr/bin/ruby -Ku

#require 'pp'

INF = 2<<29
loop do
  data = gets.split(nil)
  n, m = data.map{|e| e.to_i}
  
  break if n == 0 and m == 0

  road = Array.new(2).map!{Array.new(m+1).map!{Array.new(m+1, INF)}}

  # 初期化
  n.times{
    data = gets.split(nil)
    i, j, c, t = data.map{|e| e.to_i}
    road[0][i][j] = road[0][j][i] = c
    road[1][i][j] = road[1][j][i] = t
  }


#  pp road


=begin  だいくすとら
  costmap = Array.new(2).map!{Array.new(m+1)}
  2.times{|type|
    for st in 1..m do
      for gl in st..(m+1) do
        costs = Array.new(m+1, INF)
        costs[st] = 0
        
        queue = Array.new(1, st)
        while !queue.empty?
          src = queue.shift
          (m+1).times{ |dest|
            if costs[dest] > costs[src] + road[type][src][dest] then
              costs[dest] = costs[src] + road[type][src][dest]
              queue.push(dest)
            end
          }
    #      puts "queue:#{queue}"
        end
        costmap[type][st] = costs
      end
    end
  }  


          p costmap[type][i][j]
          p (costmap[type][i][k] + costmap[type][k][j])
          pp [costmap[type][i][j], (costmap[type][i][k] + costmap[type][k][j])]
  
=end  

# わーしゃるふろいど
  costmap = road
  
  2.times{|type|
    for k in 1..m do
      for i in 1..m do
        for j in 1..m do
          costmap[type][i][j] = [costmap[type][i][j], (costmap[type][i][k] + costmap[type][k][j])].min
        end
      end
    end
  }
  
#  pp costmap
  
  n = gets.to_i
  n.times{
    data = gets.split(nil)
    st, gl, type = data.map{|e| e.to_i}
    puts (st == gl) ? 0 : costmap[type][st][gl]
  }

end