#import<bits/stdc++.h>
#define endl '\n'
using namespace std;
int i,j,k,m,n,p,x,y,a[1005][1005],b[1005][1005],c[1005][1005],d[1005][1005],z[1005][1005];
char s[1005][1005];
void f(int i,int j)
{
	if(z[i][j])return;
	z[i][j]=k;
	if(~a[i][j])f(a[i][j],j);
	if(~b[i][j])f(i,b[i][j]);
	if(c[i][j]<n)f(c[i][j],j);
	if(d[i][j]<m)f(i,d[i][j]);
}
main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(;i<n;i++)cin>>s[i];
	for(;j<m;j++) // a : U
	{
		for(i=0,k=-1;i<n;i++)
		{
			a[i][j]=k;
			if(s[i][j]&1)k=i;
		}
	}
	for(i=0;i<n;i++) // b : L
	{
		for(j=0,k=-1;j<m;j++)
		{
			b[i][j]=k;
			if(s[i][j]&1)k=j;
		}
	}
	for(j=m;j--;) // c : D
	{
		for(i=k=n;i--;)
		{
			c[i][j]=k;
			if(s[i][j]&1)k=i;
		}
	}
	for(i=n;i--;) // d : R
	{
		for(j=k=m;j--;)
		{
			d[i][j]=k;
			if(s[i][j]&1)k=j;
		}
	}
	for(i=n-1;--i;)
	{
		if(b[i][m-1]<0&&d[i][0]==m)x++;
	}
	for(j=m-1;--j;)
	{
		if(a[n-1][j]<0&&c[0][j]==n)y++;
	}
	p=min(x,y);
	for(i=k=0;i<n;i++)
	{
		if(s[i][0]&1&&!z[i][0])
		{
			k++;
			f(i,0);
		}
		if(s[i][m-1]&1&&!z[i][m-1])
		{
			k++;
			f(i,m-1);
		}
	}
	for(j=0;j<m;j++)
	{
		if(s[0][j]&1&&!z[0][j])
		{
			k++;
			f(0,j);
		}
		if(s[n-1][j]&1&&!z[n-1][j])
		{
			k++;
			f(n-1,j);
		}
	}
	for(i=k=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			if(s[i][j]&1&&!z[i][j])
			{
				k++;
				f(i,j);
			}
		}
	}
	cout<<p+k;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const double pi = 3.14159265358979;
const ll inf = 1e17;
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
#define pii pair<int,int>
#define pll pair<ll,ll>
#define endl "\n"
#define dtor(deg) (((deg)/360)*2*pi)
#define all(a) a.begin(),a.end()
#define overload(_1,_2,_3,_4,name,...) name
#define _rep1(n) for(int i = 0; i < (n); i++)
#define _rep2(i,n) for(int i = 0; i < (n); i++)
#define _rep3(i,a,b) for(int i = (a); i < (b); i++)
#define _rep4(i,a,b,c) for(int i = (a); i < (b); i += (c))
#define rep(...) overload(__VA_ARGS__,_rep4,_rep3,_rep2,_rep1)(__VA_ARGS__)
#define _rrep1(n) for(int i = (n) - 1; i >= 0; i--)
#define _rrep2(i,n) for(int i = (n) - 1; i >= 0; i--)
#define _rrep3(i,a,b) for(int i = (b) - 1; i >= (a); i--)
#define _rrep4(i,a,b,c) for(int i = (b) - 1; i >= (a); i -= (c))
#define rrep(...) overload(__VA_ARGS__,_rrep4,_rrep3,_rrep2,_rrep1)(__VA_ARGS__)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
#define vv(type,name,size,...) vector<vector<type>> name(size,vector<type>(__VA_ARGS__))
#define ForEach(a,b) for_each(a.begin(),a.end(),b)
template <class T> bool chmin(T& a, T b){ if(a > b){ a = b; return 1; } return 0; }
template <class T> bool chmax(T& a, T b){ if(a < b){ a = b; return 1; } return 0; }

struct WeightedGraph{
    struct Edge { int to; ll cost; Edge(int to, ll cost) : to(to), cost(cost) {} };
    vector<vector<Edge>> g;
    WeightedGraph(int n) : g(n) {}
    vector<Edge> operator[](int a){ return g[a]; }
    operator vector<vector<Edge>>(){ return g; }
    auto begin(){ return g.begin(); }
    auto end(){ return g.end(); }
    int size(int x){ return g.size(); }
    void resize(int x){ g.resize(x); }
    void DirectConnect(int f, int t, ll c){ g[f].push_back({t, c}); }
    void Connect(int a, int b, ll c){ g[a].push_back({b, c}); g[b].push_back({a, c}); }
    vector<ll> dijkstra(int s){
        int n = g.size();
        vector<ll> dist(n, inf);
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> task;
        dist[s] = 0;
        task.push({dist[s], s});
        while(task.size()){
            pii p = task.top();
            task.pop();
            int v = p.second;
            if(dist[v] < p.first) continue;
            for(auto e : g[v]) if(chmin(dist[e.to], dist[v] + e.cost)) task.push({dist[e.to], e.to});
        }
        return dist;
    }
    vector<int> topo_sort(){
        int n = g.size();
        WeightedGraph copy(n);
        vector<int> deg(n);
        vector<int> order;
        queue<int> task;
        rep(n) for(auto v : g[i]){
            copy.DirectConnect(v.to, i, v.cost);
            deg[i]++;
        }
        rep(n) if(!deg[i]) task.push(i);
        while(task.size()){
            int fv = task.front();
            task.pop();
            order.push_back(fv);
            for(auto nv : copy[fv]){
                deg[nv.to]--;
                if(!deg[nv.to]) task.push(nv.to);
            }
        }
        reverse(all(order));
        return order;
    }
};

void Main(){
    int n, m;
    cin >> n >> m;
    WeightedGraph g(n), r(n);
    vector<vector<ll>> cycle(n);
    rep(m){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        a--; b--;
        if(a == b) cycle[a].push_back(c);
        else{ g.DirectConnect(a, b, c); r.DirectConnect(b, a, c); }
    }
    rep(n){
        ll ans = inf;
        vector<ll> t = g.dijkstra(i), tr = r.dijkstra(i);
        for(auto x : cycle[i]) chmin(ans, x);
        rep(j,n) if(i != j) chmin(ans, t[j] + tr[j]);
        if(ans == inf) cout << -1 << endl;
        else cout << ans << endl;
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(10) << fixed;
    Main();
}