require 'scanf'

n,m=STDIN.gets.scanf("%d %d")
graph=Array.new(m+1).map{Array.new(m+1,nil)}
for i in 0..n-1 do
    a,b,cost,time = STDIN.gets.scanf("%d %d %d %d")
    graph[a][b]=graph[b][a]=[time,cost]
end

def calc(list)
    cost,time=0,0
    for i in 0..list.length-2 do
        a,b = list[i],list[i+1]
        time = time+$graph[a][b][0]
        cost = cost+$graph[a][b][1]
    end
    return [time,cost]
end

def go(list,dest)
    cur = list[list.length-1]
    if cur==dest then
        time,cost=calc(list)
        $min_time = time if time < $min_time
        $min_cost = cost if cost < $min_cost
        return
    end
    for i in 1..$m do
        if $graph[cur][i]!=nil and \
           (not list.include?i) then
            new_list = list.clone
            new_list.push(i)
            go(new_list,dest)
        end
    end
end

n=STDIN.gets.to_i
for i in 0..n-1 do
    p,q,r=STDIN.gets.scanf("%d %d %d")
    $min_time,$min_cost=1000*3000*10000,1000*3000*10000
    $m = m
    $graph = graph
    list,dest=[p],q
    if p==q then
        $min_cost,$min_time=0,0
    else
        go(list,dest)
    end
    print $min_cost,"\n" if r==0
    print $min_time,"\n" if r==1
end
dummy = STDIN.gets