INF = 2 << 32
 
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)|
    puts "accept block: node: #{m}"
    dic = Array.new(2) {|t|
      Array.new(m + 1) {|i|
        a = Array.new(m + 1, INF)
        a[i] = 0
        a
      }
    }
    puts 'init'
 
    # load
    lines.each {|(a, b, c_0, c_1)|
      dic[0][a][b] = c_0
      dic[0][a][b] = c_0
      dic[1][a][b] = c_1
      dic[1][a][b] = c_1
    }
    puts 'load'
 
    # calc
    [0, 1].each {|t|
      (1..m).each {|i|
        (1..m).each {|j|
          (1..m).each {|k|
            dic[t][i][j] = [dic[t][i][j], dic[t][i][k] + dic[t][k][j]].min
          }
        }
      }
    }
    puts 'calc'
 
    issues.map {|start, goal, cost_type|
      # fetch
      dic[cost_type][start][goal]
    }
  }
  .each(&method(:puts))