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,b,0]=>0}
(t,u,v,w=e.flat_map{|(i,j,k),l|([[i,j-1,2],[i-1,j,3],[i,j+1,0],[i+1,j,1]].values_at(*([*0..3]-[k]))).map{|x,y,z|o=l+d[i<x ?i:x][j<y ?j:y][z%2]
x>=0&&x<m&&y>0&&y<=n&&(!(r=s[x][y])||o/r%2!=z%2)&&[o,x,y,z]}}.reject{|i,j,k,l|!i||e[[j,k,l]]}.min
e[[u,v,w]]=t)until (0..3).any?{|i|a=e[c+[i]]}
p a
end