#include <bits/stdc++.h>
using i64 = long long;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    std::vector<std::tuple<int, int, int>> es;
    std::vector<std::pair<int, int>> w;
    for (int i = 0; i < m; i++) {
        int p, q, c;
      	scanf("%d%d%d", &p, &q, &c);
        --p; --q;
        es.emplace_back(p, q, c);
        w.emplace_back(p, c);
        w.emplace_back(q, c);
    }

    std::sort(w.begin(), w.end());
    w.erase(std::unique(w.begin(), w.end()), w.end());

    auto get = [&](int v, int c) {
        return n + std::lower_bound(w.begin(), w.end(), std::make_pair(v, c)) - w.begin();
    };

    std::vector<std::vector<std::pair<int, int>>> g(w.size() + n);
    for (const auto &e : w) {
        int v = get(e.first, e.second);
        g[e.first].emplace_back(v, 1);
        g[v].emplace_back(e.first, 0);
    }
    for (const auto &e : es) {
        auto p = std::get<0>(e), q = std::get<1>(e), c = std::get<2>(e);
        int pv = get(p, c), qv = get(q, c);
        g[pv].emplace_back(qv, 0);
        g[qv].emplace_back(pv, 0);
    }

    constexpr int inf = std::numeric_limits<int>::max() / 2;
    std::vector<int> dist(g.size(), inf);
    std::deque<int> q { 0 };
    dist[0] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop_front();
        for (auto to : g[v]) {
            if (dist[to.first] <= dist[v] + to.second) continue;
            dist[to.first] = dist[v] + to.second;
            if (to.second) q.push_back(to.first);
            else q.push_front(to.first);
        }
    }

	printf("%d\n", dist[n - 1] == inf ? -1 : dist[n - 1]);
  
    return 0;
}

#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
using namespace std;
long long int inf = 10000000000;

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int main(){
  long long int n, m;
  cin >> n >> m;

  vector< vector<long long int> > dist(n, vector<long long int>(n, inf));

  for(int i=0; i<m; i++){
    int s, t, d;
    cin >> s >> t >> d;
    dist[s][t] = d;
  }
  for(int i=0; i<n; i++) dist[i][i] = 0;

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if( dist[j][i] == inf ) continue;
      for(int k=0; k<n; k++){
        if( dist[i][k] == inf ) continue;
        if( dist[j][k] > dist[j][i] + dist[i][k] ) dist[j][k] = dist[j][i] + dist[i][k];
      }
    }
  }

  for(int i=0; i<n; i++){
    if( dist[i][i] < 0 ){
      cout << "NEGATIVE CYCLE" << endl;
      return 0;
    }
  }

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if( dist[i][j] == inf ) cout << "INF";
      else cout << dist[i][j];
      if( j == n-1 ) cout << endl;
      else cout << " ";
    }
  }

  return 0;
}





// EOF