#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
	long long sum=0,naga=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')naga=-1;ch=getchar();}
	while(ch<='9'&&ch>='0')sum=sum*10+ch-'0',ch=getchar();
	return sum*naga;
}
inline void write(long long X)
{
	if(X<0)putchar('-'),X=-X;
	if(X>9)write(X/10);
	putchar(X%10+'0');
}
typedef pair<int,int>ss;
priority_queue <ss,vector<ss>,greater<ss> >q;
const long long N=1e6+5,M=5e6+5,INF=1e15;
long long head[N],n,m,s,cnt,dis[N],a,b;
bool vis[N];
struct point
{
	int u,v,w;
}edge[M];
inline void dijkstra()
{
	while(!q.empty())
	{
		ss mmp=q.top();
		int u=mmp.second;vis[u]=0,q.pop();
		for(register int i=head[u];i!=0;i=edge[i].u)
		{
			int V=edge[i].v;
			if(dis[V]>dis[u]+edge[i].w)
			{
				dis[V]=dis[u]+edge[i].w;
				if(vis[V]==0)vis[V]=1,q.push(ss{dis[V],V});
			}
		}
	}
}
inline void addedge(int u,int v,int w)
{
	edge[++cnt].u=head[u],edge[cnt].v=v,edge[cnt].w=w,head[u]=cnt;
//	edge[++cnt].u=head[u+n],edge[cnt].v=v,edge[cnt].w=w,head[u+n]=cnt;
}
int ww,id[1009][1009];
int main()
{
	a=read(),b=read();n=a*b;
	for(register int i=1;i<=a;i++)	
		for(register int j=1;j<=b;j++)
			id[i][j]=(i-1)*b+j;
	for(register int i=1;i<=a;i++)
		for(register int j=1;j<b;j++)	
		{
			ww=read();
			addedge(id[i][j],id[i][j+1],ww);
			addedge(id[i][j]+n,id[i][j+1],ww);
			addedge(id[i][j+1],id[i][j],ww);
			addedge(id[i][j+1]+n,id[i][j],ww);
		}
	for(register int i=1;i<a;i++)
		for(register int j=1;j<=b;j++)
		{
			ww=read();
			addedge(id[i][j],id[i+1][j],ww);
			addedge(id[i][j]+n,id[i+1][j],ww);
		}
	for(register int i=1;i<=a;i++)
		for(register int j=1;j<=b;j++)
			if(i!=1)addedge(id[i][j],id[i-1][j]+n,2);
	for(register int i=1;i<=a;i++)
		for(register int j=1;j<=b;j++)
			if(i!=1)
			{
				addedge(id[i][j]+n,id[i-1][j]+n,1);
				addedge(id[i][j]+n,id[i-1][j],1);
			}
	s=1;
	for(register int i=1;i<=n*2;i++)dis[i]=INF;
	q.push(ss{0,s}),dis[s]=0,vis[s]=1;
	dijkstra();
	write(dis[n]),putchar(' ');
}

#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define cl(x,v) memset((x), (v), sizeof(x))
#define db(x) cerr << #x << " == " << x << endl
#define dbs(x) cerr << x << endl
#define _ << ", " <<

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int, pii> piii;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> plll;
typedef vector<int> vi;
typedef vector <vi> vii;

const ld EPS = 1e-9, PI = acos(-1.);
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f, MOD = 1e9+7;
const int N = 2e5+5;

int cost = 0;
vector <piii> edges;
vector <pii> adj[N];

int par[N], sz[N], vis[N];

int find (int a) { return par[a] == a ? a : par[a] = find(par[a]); }

void unite (int a, int b) {
    if ((a = find(a)) == (b = find(b))) return;
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
}

void dfs(int u){
    for(auto v: adj[u]){
        if(!vis[v.nd]){
            if(vis[u] == v.st) vis[v.nd] = (v.st == 1 ? 2 : 1);
            else{
                vis[v.nd] = v.st;
            }
            dfs(v.nd);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin  >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v,c;
        cin >> u >> v >> c;
        edges.pb({c,{u,v}});
    }
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    sort(edges.begin(),edges.end());
    for(auto e : edges){
        if(find(e.nd.st) != find(e.nd.nd)){
            adj[e.nd.st].pb({e.st,e.nd.nd});
            adj[e.nd.nd].pb({e.st,e.nd.st});
            //cout << e.nd.nd << " " << e.nd.st << "\n";
            unite(e.nd.st, e.nd.nd); 
        }
    }
    vis[1] = 1;
    dfs(1);
    for(int i=1;i<=n;i++) cout << vis[i] << "\n";
    return 0;
}