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