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

#define maxn 50005
#define inf (1<<29)

using namespace std;

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

int n,m;
int D[maxn],inQ[maxn],in[maxn],T[maxn];
vector< pair<int,int> >G[maxn];
queue<int>Q;

inline bool bellman_ford () {
	
	for ( int i = 2 ; i <= n ; ++i ){
		D[i] = inf;
	}
	Q.push(1); inQ[1] = 1; in[1] = 1;
	
	while ( !Q.empty() ){
		int nod = Q.front(); Q.pop(); inQ[nod] = 0;
		//if ( inQ[T[nod]] )	continue ;
		
		for ( vector< pair<int,int> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
			int vecin = itt->first,cost = itt->second;
			
			if ( D[vecin] > D[nod] + cost ){
				D[vecin] = D[nod] + cost;
				T[vecin] = nod;
				
				if ( !inQ[vecin] ){
					Q.push(vecin);
					inQ[vecin] = 1; ++in[vecin];
					
					if ( in[vecin] > n ){
						return 0;
					}
				}
			}
		}
	}
	
	return 1;
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	int x,y,c;
	for ( int i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d %d",&x,&y,&c);
		G[x].push_back(make_pair(y,c));
	}
	
	if ( bellman_ford() ){
		for ( int i = 2 ; i <= n ; ++i ){
			fprintf(g,"%d ",D[i]);
		}
		fprintf(g,"\n");
	}
	else{
		fprintf(g,"Ciclu negativ!");
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}