#include<fstream>
#include<vector>
#include<queue>

using namespace std;

#define max_n 51000
#define inf 2000000000

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct nod{
	int x;
	int c;
}nod1;


vector< nod > L[ max_n ];

queue< int > C;

int D[max_n] , Fr[max_n] , Nr_upd[max_n];
int n , m , a , ok;

void read(){
	
	f>> n >> m;
	
	for(int i = 1; i <= m; i++){
		f>> a >> nod1.x >> nod1.c;
		
		L[a].push_back(nod1);
		
	}
	
}

void initializare(){
	
	for( int i = 2; i <= n ; i++ )
		D[i] = inf;
	
}

void solve(){
	
	initializare();
	
	C.push(1); Fr[1] = 1; Nr_upd[1] = 1;
 	
	unsigned int i ; 
	int nod1 ;
	nod nod2;
	
	while( (!C.empty()) && (!ok) ){
		
		nod1 = C.front();
		C.pop();
		
		for(i = 0; i < L[nod1].size(); i++){
			
			nod2 = L[nod1][i];
			
			if( D[nod1] + nod2.c < D[nod2.x] ){
				
				D[nod2.x] = D[nod1] + nod2.c;
				
				Nr_upd[nod2.x]++;
				
				if( Nr_upd[nod2.x] == (n-1) )
					ok = 1;
				
				if( Fr[nod2.x] == 0 ){
					
					C.push(nod2.x);
					
					Fr[nod2.x]++;
					
				}
				
			}
			
		}
		
		Fr[nod1] = 0;
	}
	
	
}


void print(){
	
	if( ok ){
		g<<"Ciclu negativ!";
		return;
	}
	
	for(int i = 2; i <= n; i++)
		g<<D[i]<<" ";
	
}


int main(){
	
	read();
	
	solve();
	
	print();
	
	return 0;
}