class PriorityQueue
    def initialize
        @priority_queue = {}
    end

    def push(priority, var)
        @priority_queue[priority] ||= []
        @priority_queue[priority] << var
    end

    def pop
        min_key = @priority_queue.keys.min
        return_var = @priority_queue[min_key].shift
        @priority_queue.delete(min_key) if @priority_queue[min_key].length == 0
        return return_var
    end

    def empty?
        @priority_queue.empty?
    end
end

class Node
    attr_reader :name, :check, :from_node
    attr_accessor :cost

    def initialize(node_data)
        @name, @cost, @to_nodes = node_data[:name], node_data[:cost], node_data[:to_node]
        @check = @from_node = nil
    end

    def node_check(dijkstras)
        @to_nodes.each do |to_node|
            node = dijkstras.nodes[to_node[:name].to_sym]
            next if node.check
            node.cost_check(to_node[:cost] + @cost, self)
            dijkstras.priority_queue.push(node.cost, node)
        end
        self
    end

    def done
        @check = true
    end

    def cost_check(cost, from_node)
        if @cost == nil || @cost > cost
            @cost = cost
            @from_node = from_node
        end
    end
end

class Dijkstras
    attr_accessor :nodes, :priority_queue

    def initialize(nodes_data, start_node_name, goal_node_name)
        @priority_queue = PriorityQueue.new
        @nodes = {}
        nodes_data.each do |node_data|
            node = Node.new(node_data)
            @nodes[node.name.to_sym] = node
        end
        @start_node = nodes[start_node_name.to_sym]
        @goal_node = nodes[goal_node_name.to_sym]
    end

    def route_check
        @start_node.cost = 0
        @priority_queue.push(@start_node.cost, @start_node)

        while(!@priority_queue.empty?)
            done_node = @priority_queue.pop
            next if done_node.check
            done_node.node_check(self).done
        end
    end

    def print_route
        current_node = @goal_node
        print current_node.name
        while((current_node = current_node.from_node) != nil)
            print " -> #{current_node.name}"
        end
    end
end

loop do
    n, m = gets.split.map(&:to_i)
    break if n == 0 && m == 0
    ds = n.times.map{gets.split.map(&:to_i)}
    k = gets.to_i
    qs = k.times.map{gets.split.map(&:to_i)}
    costs = Array.new(m+1)
    times = Array.new(m+1)
    1.upto(m) do |i|
        costs[i] = Hash.new
        costs[i][:name] = i.to_s
        costs[i][:cost] = nil
        costs[i][:to_node] = Array.new
        times[i] = Hash.new
        times[i][:name] = i.to_s
        times[i][:cost] = nil
        times[i][:to_node] = Array.new
    end
    ds.each do |d|
        costs[d[0]][:to_node] += [{:name => d[1].to_s, :cost => d[2]}]
        costs[d[1]][:to_node] += [{:name => d[0].to_s, :cost => d[2]}]
        times[d[0]][:to_node] += [{:name => d[1].to_s, :cost => d[3]}]
        times[d[1]][:to_node] += [{:name => d[0].to_s, :cost => d[3]}]
    end
    costs = costs[1...costs.size]
    times = times[1...times.size]
    dijcs = Array.new(m+1)
    dijts = Array.new(m+1)
    1.upto(m) do |i|
        dijcs[i] = Dijkstras.new(costs, i.to_s, (m - 1).to_s)
        dijcs[i].route_check
        dijts[i] = Dijkstras.new(times, i.to_s, (m - 1).to_s)
        dijts[i].route_check
    end
    puts dijcs[1].nodes[:"1"].cost

    qs.each do |q|
        case q[2]
        when 0
            puts dijcs[q[0]].nodes[q[1].to_s.to_sym].cost
        when 1
            puts dijts[q[0]].nodes[q[1].to_s.to_sym].cost
        end
    end
end