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

#define INF 1<<30
#define Nmax 50005

using namespace std;

vector < pair <int, int> > A[Nmax];

int sol[Nmax], d[10*Nmax], viz[Nmax], viz2[Nmax];
int n, m, i, a, b, c, p, u, nod, ok, l, fiu;

void BFS(){
	
	p = 1;
	u = 1;
	d[p] = 1;
	viz[1] = 1;
	
	while (p <= u && u < 10 * Nmax){
		nod = d[p];
		l = (int)A[nod].size();
		
		for (i = 0 ; i < l ; i++){
			fiu = A[nod][i].first;
			a = sol[fiu];
			sol[fiu] = min ( sol[nod] + A[nod][i].second, sol[fiu] );
			
			if (a != sol[fiu])
				viz[fiu] = 0;
			
			if (viz[fiu] == 0){
				d[++u] = fiu;
				viz[fiu] = 1;
				viz2[fiu] ++;
			}
		}
		
		++p;
	}
}

int main (){
	
	FILE * f = fopen ("bellmanford.in", "r");
	FILE * g = fopen ("bellmanford.out", "w");
	
	fscanf (f, "%d %d", &n, &m);
	for (i = 1 ; i <= m ; i++){
		fscanf (f, "%d %d %d", &a, &b, &c);
		A[a].push_back ( make_pair (b, c) );		
	}
	
	for (i = 2 ; i <= n ; i++)
		sol[i] = INF;

	BFS();
	
	ok = 1;
	
	for (i = 1 ; i <= n ; i++)
		if (viz2[i] >= n-1) {
			fprintf (g, "Ciclu negativ!");
			ok = 0;
			break;
		}
	
	if ( ok ){
		for (i = 2 ; i <= n ; i++)
			if (sol[i] != INF )
				fprintf (g, "%d ", sol[i]);
			else 
				fprintf(g, "0 ");
	}
	fclose(f);
	fclose(g);
	return 0;
}