#include <stdio.h>
#define N 50001
#define INF 1<<30
FILE *f=fopen ("bellmanford.in", "r");
FILE *g=fopen ("bellmanford.out", "w");
struct nod { int x,y,c;	}	v[5*N];
int n,m,c[N];

void citire() {
int i;
fscanf (f, "%d%d", &n,&m);
for (i=1;i<=m;i++)
	fscanf (f, "%d%d%d", &v[i].x,&v[i].y,&v[i].c);

for (i=2;i<=n;i++)
	c[i]=INF;
}

int bf() {
int i,j,sw=1;

for (i=1;i<=n && sw;i++)
{
	sw=0;
	for (j=1;j<=m;j++)
		if ( c[v[j].y] > c[v[j].x] + v[j].c )
		{
			c[v[j].y]=c[v[j].x]+v[j].c;
			sw=1;
		}
}

for (i=1;i<=m;i++)
	if ( c[v[i].y] > c[v[i].x] + v[i].c )
		return 0;

return 1;
}

int main() {
citire();

if ( bf() )
	for (int i=2;i<=n;i++)
		fprintf (g, "%d ", c[i]);
else
	fprintf (g, "Ciclu negativ!");

return 0;
}