#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>

#define maxN 50005
#define INF (1<<30)

using namespace std;

FILE*f=fopen("bellmanford.in","r");
FILE*g=fopen("bellmanford.out","w");

int n,m,x,y,c,i,D[maxN],viz[maxN];
vector< pair<int,int> >G[maxN];
queue<int>Q; int qsize,nod;
bitset<maxN>inQ;

inline void citire () {
	
	fscanf(f,"%d %d",&n,&m);
	
	for ( i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d %d",&x,&y,&c);
		G[x].push_back( make_pair(y,c) );
	}
}

inline bool bellman_ford () {
	
	Q.push(1); qsize = inQ[1] = viz[1] = 1; 
	
	while ( qsize ){
		
		nod = Q.front(); Q.pop(); --qsize; inQ[nod] = 0;
		
		for ( i = 0 ; i < G[nod].size() ; ++i ){
			if ( D[ G[nod][i].first ] > D[nod] + G[nod][i].second ){
				D[ G[nod][i].first ] = D[nod] + G[nod][i].second;
				
				if ( !inQ[ G[nod][i].first ] ){
					inQ[ G[nod][i].first ] = 1;
					if ( ++viz[ G[nod][i].first ] >= n )
						return 0;
					Q.push( G[nod][i].first ); ++qsize;
				}
			}
		}
	}
	
	return 1;
}

inline void solve () {
	
	for ( i = 2 ; i <= n ; ++i ){
		D[i] = INF;
	}
	
	if ( bellman_ford() ){
		for ( i = 2 ; i <= n ; ++i ){
			fprintf(g,"%d ",D[i]);
		}
		fprintf(g,"\n");
	}
	else{
		fprintf(g,"Ciclu negativ!");
	}
}

int main () {
	
	citire();
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}