// E - 潜入
#include <bits/stdc++.h>
using namespace std;
#define vec vector
using vi = vec<int>;
using PR = pair<int,int>;
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int V; // 頂点数
vec<vec<PR>> G; // [from]<to, cost> 隣接リスト
int INF = 1e9;

vi dijkstra(int s){
	vi dist(V, INF);
	dist[s] = 0;
	priority_queue<PR, vec<PR>, greater<PR>> pq;
	pq.push({0, s});
	while(pq.size()){
		auto[from_d, from_v] = pq.top(); pq.pop();
		if(dist[from_v] < from_d) continue;
		for(auto[to_u, to_d]:G[from_v]){
			to_d += dist[from_v];
			if(dist[to_u] <= to_d) continue;
			dist[to_u] = to_d;
			pq.push({to_d, to_u});
		}
	}
	return dist;
}

int main(){
	int R, C; cin>>R>>C;
	vec<vi> A(R, vi(C-1)); for(vi&v:A) for(int&x:v) cin>>x;
	vec<vi> B(R-1, vi(C)); for(vi&v:B) for(int&x:v) cin>>x;
	auto rc2id = [&](int r, int c){ return r*C + c; };
	V = R*C*2;
	G.resize(V);
	rep(r, R) rep(c, C){
		int a = rc2id(r, c), b = rc2id(r, c+R*C);
		G[a].emplace_back(b, 1), G[b].emplace_back(a, 0);
		if(r != R-1){
			G[rc2id(r+1, c+R*C)].emplace_back(rc2id(r, c+R*C), 1);
			G[rc2id(r, c)].emplace_back(rc2id(r+1, c), B[r][c]);
		}
		if(c != C-1){
			a = rc2id(r, c), b = rc2id(r, c+1);
			G[a].emplace_back(b, A[r][c]), G[b].emplace_back(a, A[r][c]);
		}
	}
	cout<< dijkstra(0)[rc2id(R-1,C-1)] <<endl;
}

#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define mt make_tuple
#define eb emplace_back
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mem(arr,x) memset(arr, x, sizeof arr)
#define db(arr) for(auto x : arr) cout << x << " "; cout << "\n";
#define db2d(arr) for(auto x : arr){ for(auto y : x) cout << y << " "; cout << "\n";}
#define read(arr) for(auto &x : arr) cin >> x;
#define sz(x) (int)x.size()
#define MOD 1000000007
#define MOD2 998244353
#define nl '\n'
using namespace std;

// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (k) : Number of items strictly smaller than k 
// find_by_order(k) : K-th element in a set (counting from zero)

string to_string(char c) {
	return string(1, c);
}

string to_string(bool b) {
	return b ? "true" : "false";
}

string to_string(const char* s) {
	return string(s);
}

string to_string(string s) {
	return s;
}

string to_string(vector < bool > v) {
	string res;
	for(int i = 0; i < sz(v); i++)
		res += char('0'+v[i]);
	return res;
}
 
template < size_t S > string to_string(bitset < S > b) {
	string res;
	for(int i = 0; i < S; i++)
		res += char('0' + b[i]);
	return res;
}

template < class T > string to_string(T v) {
    bool f = 1;
    string res;
    for(auto x : v) {
		if(!f)
			res+=' ';
		f=0;
		res += to_string(x);
	}
    return res;
}
 
void dbvar() { cerr << "]" << endl; }
template<class H, class... T> void dbvar(H h, T... t){
	cerr << to_string(h);
	if(sizeof...(t))
		cerr << ", ";
	dbvar(t...);
}

template<class A> void write(A x) {
	cout << to_string(x);
}

template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h);
	write(t...);
}

void print() {
	write("\n");
}

template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h);
	if(sizeof...(t))
		write(' ');
	print(t...);
}

template <typename T1, typename T2>
constexpr typename std::common_type<T1, T2>::type floor_div(T1 x, T2 y) {
	assert(y != 0);
	if (y < 0) x = -x, y = -y;
	return x < 0 ? (x - y + 1) / y : x / y;
}

const ll INFL = (ll)1e18;
const int INF = (int)1e9;
const ld eps = (ld)1e-9;
const ld pi = acos(-1.0);
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

ll power(ll n, ll m){
	if(m == 0) return 1;
	ll val = power(n, m/2);
	if(m % 2 == 0) return (val * val); else return ((val * val) * n);
}

ll powermod(ll n, ll m, ll _MOD){
	if(m == 0) return 1;
	ll val = powermod(n,m/2,_MOD);
	val %= _MOD;
	if(m % 2 == 0) return (val * val) % _MOD; else return (((val * val) % _MOD) * n) % _MOD;
}

const int mxN = 3000;
vector < pair < ll, ll > > graph[mxN];
ll dis[mxN];
void solve(){
	ll n, m; cin >> n >> m;
	for(ll i = 0; i < m; i++){
		ll a, b, c; cin >> a >> b >> c; a--; b--;
		graph[a].pb(MP(b, c));
	}
	priority_queue < pair < ll, ll >, vector < pair < ll, ll > >, greater < pair < ll, ll > > > q;
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < mxN; j++) dis[j] = INF;
		dis[i] = 0;
		ll ans = INF;
		q.push(MP(0, i));
		while(!q.empty()){
			auto cur = q.top(); q.pop();
			if(cur.first > dis[cur.second]) continue;
			for(auto x : graph[cur.second]){
				if(dis[x.first] > cur.first + x.second){
					dis[x.first] = cur.first + x.second;
					q.push(MP(dis[x.first], x.first));
				}
				if(x.first == i){
					ans = min(ans, cur.first + x.second);
				}
			}
		}
		if(ans == INF) ans = -1;
		print(ans);
	}
}

int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);

	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif

	// cout << setprecision(10) << fixed;
	
	int t = 1;
	// cin >> t;

	for(int i = 1; i <= t; i++){
		// cout << "Case #" << i << ": ";
		solve();
	}

	return 0;
}