def g;gets.gsub(/[a-z]/){$&.ord-97}.split(/-| /).map &:to_i;end
while(m,n=g)[0]>0
d=g[0]
s=(1..m).map{[]}
d=(1..m).map{(0..n).map{[d,d]}}
g[0].times{h,v,k=g;s[h][v]=k}
2.times{g[0].times{h,v,i,w,k=g;d[h<i ?h:i][v<w ?v:w][h==i ?0:1]+=k||101}}
a,b,*c=g
e={a=[0,a,b,0]=>0}
t,u,v,w=*a
q=[]
([[u,v-1,2],[u-1,v,3],[u,v+1,0],[u+1,v,1]].reject{|x,y,z|(z-2)%4==w||x<0||x>=m||y<=0||y>n}.map{|i|x,y,z=i
o=t+d[u<x ?u:x][v<y ?v:y][z%2]
(!(r=s[x][y])||o/r%2!=z%2)&&[o]+i}.map{|i|i&&!e[i]&&q[q.index{|j|i[0]>j[0]}||q.size,0]=[i]}
e[(t,u,v,w=q.pop)]=t
)until[u,v]==c
p t
end