#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50050
#define INF 0x3f3f3f3f

bool viz[NMAX];
int C[NMAX], in[NMAX], n, m;
vector < pair <int, int> > G[NMAX];
queue <int> Q;

bool bellman_ford ();
void citire (), afisare ();

int main () {
	
	citire ();
	
	afisare ();
	
	return 0;
}

bool bellman_ford () {
	
	int nod, fiu, cst;
	vector < pair <int, int> >::iterator it;
	
	memset (C, INF, sizeof (C));
	
	Q.push (1), C[1] = 0, viz[1] = 1;
	while (!Q.empty ()) {
		nod = Q.front ();
		
		for (it = G[nod].begin (); it != G[nod].end (); it++) {
			fiu = it -> first, cst = it -> second;
			
			if (C[nod] + cst < C[fiu]) {
				C[fiu] = C[nod] + cst;
				
				if (!viz[fiu]) Q.push (fiu), viz[fiu] = 1, in[fiu]++;
				
				if (in[fiu] > n) return 0;
			}
		}
		
		Q.pop (), viz[nod] = 0;
	}
	
	return 1;
}

void citire () {
	
	freopen ("bellmanford.in", "r", stdin);
	
	int i, x, y, c;
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d %d", &x, &y, &c);
		G[x].push_back (make_pair (y, c));
	}
}

void afisare () {
	
	freopen ("bellmanford.out", "w", stdout);
	
	if (bellman_ford ())
		for (int i = 2; i <= n; i++) printf ("%d ", C[i]);
	else
		printf ("Ciclu negativ!");
}