/*     *******************Bismillahir Rahmanir Rahim************************
                          MD. ASFAKUL GHANI!
                          *ProMAGFAT*!
 SECRET_warning :)->FAT   CSE-25!
                          JAHANGIRNAGAR UNIVERSITY!
                          Dhaka,Bangladesh!
*/

#include <bits/stdc++.h>
#include <set>
using namespace std;

#define           fasterIO ios_base::sync_with_stdio(false);cin.tie(NULL)
#define           Im int main()
#define           ll long long
#define           sc scanf
#define           pf printf
#define           rn0 return 0
#define           rn return
#define           f0(i,n) for(ll i=0;i<n;i++)
#define           f1(i,n) for(ll i=1;i<=n;i++)
#define           f2(i,n) for(ll i=n-1;i>=0;i--)
#define           pi 2*acos(0.0)
#define           modulo 1000003
#define           dd double
#define           PI 3.14159265358979
#define           pi 2*acos(0.0)
#define           p_b push_back
#define           ps push

/*
ll for_binarySearch(ll a,ll b,ll aa[],ll x){while(a<=b){ll mid=(a+b)/2;if(aa[mid]==x) return 1;else if(aa[mid] > x) b=mid-1;else a=mid+1;}return -1;}
ll for_gcd(ll a,ll b){if(a==0) return b;else return for_gcd(b%a,a);}
ll for_prime(ll x){for (ll i=2;i*i<=x;i++){if(x%i==0) return 0;}return 1;}
void for_swap(char *x,char *y){char temp;temp=*x;*x=*y;*y=temp;}
ll for_big_mod(ll b,ll p,ll m){if(p==0) return 1;else if(p%2==0){ll k=for_big_mod(b,p/2,m);return (k*k)%m;}else return ((b%m)*(for_big_mod(b,p-1,m)))%m;}
ll for_josephus(ll n,ll k){if(n==1) return 1;return (for_josephus(n-1,k)+k-1)%n+1;}
ll for_gcdExtended(ll a,ll b,ll *x,ll *y){if(a==0){*x=0;*y=1;return b;}ll x1,y1;ll gcd=for_gcdExtended(b%a,a,&x1,&y1);*x=y1-(b/a)*x1;*y=x1;return gcd;}
*/

void debug1()
{
    cout << "***" << endl;
}

void debug11(ll n)
{
    cout << n << endl;
}

#define ipair pair <ll,ll>
#define inf 12345678912345
ll n,m,p;
vector <ipair> v1[101010];
pair <ll,ipair> pp[101010];
vector <ll> dis;

void FAT_dj(ll src)
{
    priority_queue <ipair, vector<ipair>, greater<ipair> > pq;
    pq.ps(make_pair(0,src));
    dis[src] = 0;
    while (!pq.empty()){
        ll u = pq.top().second;
        pq.pop();
        vector <ipair> ::iterator it;
        for (it = v1[u].begin(); it != v1[u].end(); it += 1){
            ll v = (*it).first;
            ll w = (*it).second;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                pq.ps(make_pair(dis[v],v));
            }
        }
    }
}

void FAT_Ncycle(ll src)
{
    dis[src] = 0;
    for (ll i = 0; i < n; i += 1){
        if (src == i) continue;
        for (ll j = 0; j < m; j += 1){
            ll w = pp[j].first;
            ll u = pp[j].second.first;
            ll v = pp[j].second.second;
            if (dis[u] + w < dis[v] && dis[u] != inf){
                dis[v] = dis[u] + w;
            }
        }
    }
}

Im
{
    /*#ifdef FAT
       freopen("input.txt","w",stdin);
    #endif // FAT*/

    //fasterIO;

    cin>>n>>m;

    for (ll i = 0; i < m; i += 1){
        ll u,v,w;
        cin>>u>>v>>w;
        v1[u].p_b(make_pair(v,w));
        pp[i] = make_pair(w,make_pair(u,v));
        //v1[v].p_b(make_pair(u,w));
    }

    for (ll k = 0; k < n; k += 1){
    for (ll i = 0; i <= n; i += 1) dis.p_b(inf);

    FAT_Ncycle(k);
    if (k==0){
    for (ll i = 0; i < m; i += 1){
        ll w = pp[i].first;
        ll u = pp[i].second.first;
        ll v = pp[i].second.second;
        if (dis[u] != inf && dis[u] + w < dis[v]){
            cout << "NEGATIVE CYCLE" << endl;
            rn0;
        }
    }
    }
    if (dis[0] == inf) cout << "INF";
    else cout << dis[0];
    for (ll i = 1; i < n; i += 1){
        if (dis[i] == inf) cout << " " << "INF";
        else cout << " " << dis[i];
    }
    cout << endl;
    dis.clear();
    }

    for (ll i = 0; i < n; i += 1) v1[i].clear();

   // main();

    rn0;
}
#include <bits/stdc++.h>

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
// #define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

template<typename W>
struct N003 {
   typedef std::vector<long> LI;
   typedef std::vector<W>    LW;
   long n, e;
   LI ss, ds;
   LW ws;
   std::vector<LI> iss;
   N003(long n_, const LI& ss_, const LI& ds_, const LW& ws_)
      : n(n_), e(ss_.size()), ss(ss_), ds(ds_), ws(ws_) {
      iss.resize(n+1);
      for(long i = 0; i < e; ++i) {
         iss[ss[i]].push_back(i);
      }
   }
};

template<typename W>
struct N006 {
   std::vector<std::vector<W>> xss;
   bool negativeCycle;
   N006(const N003<W>& g, W inf) : negativeCycle(false) {
      xss.resize(g.n+1);
      for(auto& xs : xss) xs.resize(g.n+1, inf);
      for(long i = 0; i < g.n+1; ++i) xss[i][i] = 0;
      for(long i = 0; i < g.e; ++i) {
         xss[g.ss[i]][g.ds[i]] = g.ws[i];
      }
      for(long z = 0; z < g.n+1; ++z) {
         for(long x = 0; x < g.n+1; ++x) {
            for(long y = 0; y < g.n+1; ++y) {
               W d = xss[x][y];
               W nd = xss[x][z] + xss[z][y];
               xss[x][y] = std::min(d, nd);
            }
         }
      }
      for(long x = 0; x < g.n+1; ++x) {
         for(long y = 0; y < g.n+1; ++y) {
            if( xss[x][y] >= inf / 2 ) {
               xss[x][y] = inf;
            }
         }
         if( xss[x][x] < 0 ) {
            negativeCycle = true;
         }
      }
   }
};

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void solve() {
      typedef std::vector<long> LI;
      long v, e;
      scan(v, e);
      LI ss(e+1), ds(e+1);
      LI ws(e+1);
      for(long i = 0; i < e; ++i) {
         scan(ss[i], ds[i], ws[i]);
      }
      N003<long> g(v, ss, ds, ws);
      N006<long> warshallfloyd(g, (1LL << 60));
      if( warshallfloyd.negativeCycle ) {
         puts("NEGATIVE CYCLE");
      }
      else {
         for(long i = 0; i < v; ++i) {
            for(long k = 0; k < v; ++k) {
               if( warshallfloyd.xss[i][k] == (1LL << 60) ) {
                  printf("INF");
               }
               else {
                  printf("%ld", warshallfloyd.xss[i][k]);
               }
               putchar( k == v - 1 ? '\n' : ' ');
            }
         }
      }
   }
};

int main() {
  loop std::unique_ptr<Solver>(new Solver())->solve();
}