#include <bits/stdc++.h>

// zamiast pisac first, second pisze a, b

#define a first
#define b second

using namespace std;

// X - dlugosc pasa, Y - ilosc pasow, DP[x][y] - najmniejsza
// liczba skretow aby dostac sie na miejsce GRAF[x][y]

// GRAF[x][y] - informacje o autostradzie, VIS[x][y] - odwiedzony

// Q - kolejka przydatna do bfs'a

// ODW - ktore indeksy odwiedzalem - przyda sie
// w optymalizacji zerowania tablicy VIS

int X, Y, DP[1001][1001]; 
bool GRAF[1001][1001], VIS[1001][1001];
queue <pair <int, int>> Q;
vector <pair <int, int>> ODW;

void bfs(int x, int y) {
	Q.push({x, y});
	DP[x][y] = 0;

	while (!Q.empty()) {
		x = Q.front().a;
		y = Q.front().b;
		Q.pop();

		if (VIS[x][y])
			continue;

		VIS[x][y] = 1;
		ODW.push_back({x, y});

		if (x < X and !GRAF[x + 1][y])
			DP[x + 1][y] = min(DP[x + 1][y], DP[x][y]), Q.push({x + 1, y});

		if (y > 1 and !GRAF[x][y - 1]) {
			DP[x][y - 1] = min(DP[x][y - 1], DP[x][y] + 1);
			if (!VIS[x][y - 1])
				Q.push({x, y - 1});
		} if (y < Y and !GRAF[x][y + 1]) {
			DP[x][y + 1] = min(DP[x][y + 1], DP[x][y] + 1);
			if (!VIS[x][y + 1])
				Q.push({x, y + 1});
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> Y >> X;

	for (int y = 1; y <= Y; y ++)
		for (int x = 1; x <= X; x ++)
			cin >> GRAF[x][y];


	// na poczatku ustawiam max wartosc na kazdym elemencie
	const int INF = 1e6 + 1;
	int wy = INF;

	for (int j = 1; j <= Y; j ++)
		for (int i = 1; i <= X; i ++)
			DP[i][j] = INF;

	for (int y = 1; y <= Y; y ++) {
		if (!GRAF[1][y])
			bfs(1, y);

		// szukam min wsrod zakonczen autostrady
		int mn = DP[X][1];
		for (int j = 2; j <= Y; j ++)
			mn = min(mn, DP[X][j]);
		wy = min(wy, mn);

		// zeruje odwiedzone elementy w tablicy VIS
		for (auto a : ODW)
			VIS[a.a][a.b] = 0;
		ODW.clear();
	}

	if (wy != INF)
		cout << wy;
	else
		cout << "NIE";
}