#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
//#define INF (1e9+1)
#define INF (1LL<<59)

#define int ll

signed main(){
    int v,e;
    cin>>v>>e;
    int d[101][101];
    rep(i,101)rep(j,101)d[i][j] = INF;
    rep(i,101)d[i][i] = 0;
    
    
    rep(i,e){
        int s,t,c;
        cin>>s>>t>>c;
        d[s][t] = c;
    }
    
    rep(k,v){
        rep(i,v){
            rep(j,v){
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    
    rep(i,v){
        if(d[i][i]<0){
            cout<<"NEGATIVE CYCLE"<<endl;
            return 0;
        }
    }
    
    rep(i,v){
        rep(j,v){
            if(j)cout<<" ";
            int res=d[i][j];
            if(res>=INF/2)cout<<"INF";
            else cout<<res;
        }
        cout<<endl;
    }
}
#include<bits/stdc++.h>
#define MAXN 1000005
#define INF int(16843009)
using namespace std;

int N,M;

struct edge{
	int u,v;
	edge(int u=0, int v=0):u(u), v(v){}
};

vector<edge> adjc[MAXN];
vector<int> adj1[MAXN];

void addE(int u, int v){
	cerr<<"addE: "<<u<<" "<<v<<endl;
	adj1[u].push_back(v);
	adj1[v].push_back(u);
}

int d[MAXN];
void bfs(){
	memset(d, 1, sizeof(d));
	d[1] = 0;
	queue<int> q;
	q.push(1);
	
	int u,v;
	while(!q.empty()){
		u = q.front(); q.pop();
		if(u==N) return;
		
		for(int k=0;k<adj1[u].size();k++){
			v = adj1[u][k];
			if(d[u] + 1 < d[v]){
				d[v] = d[u] + 1;
				q.push(v);
			}
		}
	}
}

int fa[MAXN];
int p[MAXN];
int findR(int x){
	if(p[x]==x) return x;
	else return p[x] = findR(p[x]);
}

int main(){
	
	scanf("%d%d", &N, &M);
	
	int u,v,c;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d", &u, &v, &c);
		adjc[c].push_back(edge(u,v));
	}
	
	int top = N;
	for(int i=1;i<=1e6;i++){
		//cout<<i<<endl;
		if(adjc[i].size()==0) continue;
		//
		for(int k=0;k<adjc[i].size();k++){
			u = adjc[i][k].u; v = adjc[i][k].v;
			p[u] = u; p[v] = v;
			fa[u] = fa[v] = 0;
		}
		
		int ru,rv; 
		for(int k=0;k<adjc[i].size();k++){
			u = adjc[i][k].u; v = adjc[i][k].v;
			ru = findR(u); rv = findR(v);
			p[ru] = rv;
		}
		
		for(int k=0;k<adjc[i].size();k++){
			u = adjc[i][k].u; v = adjc[i][k].v;
			ru = findR(u); rv = findR(v);
			//
			if(fa[ru]) addE(u,fa[ru]);
			else{
				fa[ru] = ++top;
				addE(u,top);
			}
			
			//
			if(fa[rv]) addE(v,fa[rv]);
			else{
				fa[rv] = ++top;
				addE(v,top);
			}
		}
	}
	//cout<<"pass"<<endl;
	bfs();
	
	if(d[N]==INF) cout<<"-1"<<endl;
	else cout<<d[N]/2<<endl;
	
	return 0;
}
