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}}
u,v,*c=g
e={[t=w=0,u,v]=>0}
q=[]
(q+=[[u,v-1,2],[u-1,v,3],[u,v+1,0],[u+1,v,1]].map{|i|x,y,z=i
(z-2)%4!=w&&x>=0&&x<m&&y>0&&y<=n&&(o=t+d[u<x ?u:x][v<y ?v:y][z%2])<101&&
(!(r=s[x][y])||o/r%2!=z%2)&&!e[[o,x,y]]&&[o]+i}-[false]
e[(t,u,v,w=q.shift)[0,3]]=0)until 1
p t
end