#include<stdio.h>
#define inf 2000000000
#define nmax 50002
#define mmax 250002
#define tmax 100
struct muchie
{
	int a,b,c;
}v[mmax];
int n,m,c[nmax];

void sol()
{
	int i,ok=1,nr=0;
	while(ok && nr<=tmax)
	{
		ok=0;
		for(i=1;i<=m;i++)
			if(c[v[i].a]+v[i].c<c[v[i].b])
			{
				c[v[i].b]=c[v[i].a]+v[i].c;
				ok=1;
			}
	}
}

bool ciclu()
{
	int i;
	for(i=1;i<=m;i++)
		if(c[v[i].a]+v[i].c<c[v[i].b])
			return 0;
	return 1;
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].c);
	for(i=2;i<=n;i++)
		c[i]=inf;
	sol();
	if(!ciclu())
		printf("Ciclu negativ!\n");
	else
		for(i=2;i<=n;i++)
			printf("%d ",c[i]);
	return 0;
}