#include <cstdio>
#define INF 0x3f3f
using namespace std;
int n,m,i,j,k,x,y;
short int c[2850][2850],d[2850];
bool flag;
bool bf()
{
	for (i=1;i<=n;i++)
	{
		flag=0;
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++)
				if (c[j][k]!=INF&&d[k]>d[j]+c[j][k])
				{
					d[k]=d[j]+c[j][k];
					flag=1;
				}
		if (!flag)
			return 0;
	}
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if (c[i][j]!=INF&&d[j]>d[i]+c[i][j])
				return 1;
	return 0;
}
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
	{
		d[i]=c[i][i]=INF;
		for (j=i+1;j<=n;j++)
			c[i][j]=c[j][i]=INF;
	}
	d[1]=0;
	for (i=0;i<m;i++)
	{
		scanf("%d%d",&x,&y);
		scanf("%hd",&c[x][y]);
	}
	if (bf())
		puts("Ciclu negativ!\n");
	else
		for (i=2;i<=n;i++)
			printf("%hd ",d[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}