def d p,q,r,m,root
    station=Array.new(m,(m+1)*(1000))
    station[q]=0
    bStation=[]
    m.times{|t|bStation.push t}
    
    while bStation.length>0
      min=(m+1)*1001
      minStation=3001
      bStation.each{|e|
        if station[e]<min
          minStation=e
          min=station[e]
        end
      }
      root.each{|e|
	if e[0]==minStation
          station[e[1]]=e[2+r]+station[e[0]] if station[e[1]]>e[2+r]+station[e[0]]
	  root.delete e
        end
      }
      bStation.delete minStation
    end
  p station[p]
end

while true
  n,m=gets.split(" ").map{|e|e.to_i}
  break if n==0 && m==0
  @root=[]
  n.times{
    a,b,c,t = gets.split(" ").map{|e|e.to_i}
    @root.push [a-1,b-1,c,t]
    @root.push [b-1,a-1,c,t]
  }


  gets.to_i.times{
    p,q,r=gets.split(" ").map{|e|e.to_i}
    d p-1,q-1,r,m,@root.clone
  }
end