def g;gets.split.map &:to_i;end
while(n,m=g)[0]>0
e=[c=(0..m).map{|i|([0]+[1e4]*m).rotate -i},c.map{|i|i.dup}]
n.times{a,b,*c=g;i=-1;e.map{|h|h[a][b]=h[b][a]=c[i+=1]}}
r=1..m
r.each{|k|r.each{|i|(i+1..m).each{|j|e.map{|h|h[i][j]>(z=h[i][k]+h[k][j])&&h[i][j]=h[j][i]=z}}}}
g[0].times{*d,c=g;a,b=d.sort;p e[c][a][b]}
end