#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#include <iostream>
#include <string>
#include <bitset>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define ALL(g) (g).begin(), (g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define pb push_back
#define mp make_pair

typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef long long ll;

const int INF = INT_MAX;

int main(void) {
    int v, e, s, t, d;
    scanf("%d %d", &v, &e);

    int g[v][v];
    rep(i, v) rep(j, v) g[i][j] = INF;
    rep(i, v) g[i][i] = 0;

    rep(i, e) {
        scanf("%d %d %d", &s, &t, &d);
        g[s][t] = d;
    }
    
    rep(k, v) {
        rep(i, v) {
            if (g[i][k] == INF) continue;
            rep(j, v) {
                if (g[k][j] == INF) continue;
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }

    int flag = 1;
    rep(i, v) {
        if (g[i][i] < 0) {
            flag = 0;
            break;
        }
    }

    if (flag) {
        rep(i, v) {
            rep(j, v) {
                if (j) printf(" ");
                if (g[i][j] == INF) printf("INF");
                else printf("%d", g[i][j]);
            }
            printf("\n");
        }
    }
    else printf("NEGATIVE CYCLE\n");

    return 0;
}
/*
    Problem 33
    https://atcoder.jp/contests/abc088/tasks/abc088_d
*/
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
vector<int> dx = {0, 0, 1, -1};
vector<int> dy = {1, -1, 0, 0};
/* function */
/* main */
int main(){
    int h, w;
    cin >> h >> w;
    vector<vector<bool>> grid(h, vector<bool>(w));
    int ans = h * w;
    for (int i = 0; i < h*w; i++) {
        char c; cin >> c;
        grid[i/w][i%w] = c == '.';
        ans -= (c == '#');  // 黒マスの分あらかじめ引いとく
    }

    vector<vector<int>> dist(h, vector<int>(w, 0));
    queue<pii> q;
    q.emplace(0, 0);
    dist[0][0] = 1;
    while(!q.empty()) {
        pii p = q.front(); q.pop();
        int x = p.first, y = p.second;
        for (int i = 0; i < dx.size(); i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || h <= nx || ny < 0 || w <= ny) continue;
            if (!grid[nx][ny] || dist[nx][ny] != 0) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.emplace(nx, ny);
        }
    }
    cout << ((dist[h-1][w-1] == 0) ? -1 : ans - dist[h-1][w-1]) << '\n';
}