#include<bits/stdc++.h>
#define N 1005
using namespace std;
int n,m,f[N][N],ans=-1;
struct z{
	int to,w;
};vector<z>b[N];
queue<z>q;
bool ok[N][N];
void bfs(){
	memset(f,-1,sizeof(f)),f[1][n]=0,q.push((z){1,n});
	while(!q.empty()){
		int x=q.front().to,y=q.front().w;q.pop();
		if(~ans&&ans<=f[x][y]*2)break;
		if(x==y){ans=f[x][y]*2;break;}
		if(ok[x][y])ans=f[x][y]*2+1;
		for(int i=0;i<b[x].size();i++)for(int j=0;j<b[y].size();j++)if(b[x][i].w==b[y][j].w){
			int A=b[x][i].to,B=b[y][j].to;
			if(f[A][B]<0)f[A][B]=f[x][y]+1,q.push((z){A,B});
		}
	}cout<<ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;char s[2];
		scanf("%d%d%s",&x,&y,s);b[x].push_back((z){y,(int)s[0]}),b[y].push_back((z){x,(int)s[0]});ok[x][y]=1,ok[y][x]=1;
	}bfs();
}
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int f[N][N];
int a[N][N],b[N][N];
struct qw{
	int x,y,v;
	bool operator < (const qw &w) const
	{
		return v>w.v;
	}
};
priority_queue<qw> heap;
int vis[N][N];
int n,m;
int check(int x,int y)
{
	if(x<1||x>n||y<1||y>m) return 0;
	return 1;
}
void dij()
{
	int nx,ny;
	while(heap.size())
	{
		qw t=heap.top();
		heap.pop();
		int x=t.x,y=t.y;
		if(x==n&&y==m) break;
		if(vis[x][y]) continue;
		vis[x][y]=1;
		nx=x,ny=y+1;
		if(check(nx,ny)&&f[nx][ny]>f[x][y]+a[x][y])
		{
			f[nx][ny]=f[x][y]+a[x][y];
			heap.push((qw){nx,ny,f[nx][ny]});
		}
		nx=x,ny=y-1;
		if(check(nx,ny)&&f[nx][ny]>f[x][y]+a[x][y-1])
		{
			f[nx][ny]=f[x][y]+a[x][y-1];
			heap.push((qw){nx,ny,f[nx][ny]});
		}
		nx=x+1,ny=y;
		if(check(nx,ny)&&f[nx][ny]>f[x][y]+b[x][y])
		{
			f[nx][ny]=f[x][y]+b[x][y];
			heap.push((qw){nx,ny,f[nx][ny]});
		}
		for(int i=1;i<x;i++)
		if(f[x-i][y]>f[x][y]+i+1)
		{
			f[x-i][y]=f[x][y]+i+1;
			heap.push((qw){x-i,y,f[x-i][y]});
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m-1;j++)
	scanf("%d",&a[i][j]);
	for(int i=1;i<=n-1;i++)
	for(int j=1;j<=m;j++)
	scanf("%d",&b[i][j]);
	memset(f,0x3f,sizeof(f));
	f[1][1]=0;
	heap.push((qw){1,1,0});
	dij();
	cout<<f[n][m];
	return 0;
}