#include<stdio.h>
#define NMAX 50001
#define MMAX 250001
#define inf 20000000
int *nod[NMAX],*cost[NMAX];
int iin,ssf,in,sf,viz[NMAX],d[NMAX],y[MMAX],q[MMAX],i,j,n,m,k,l,a,s,b,c;
struct kkt
{
	int A,B,C;
};
kkt z[MMAX];
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);

	for (i=1;i<=m;i++)
	{
		scanf("%d%d%d",&z[i].A,&z[i].B,&z[i].C);
		y[z[i].A]++;
	}

	for (i=1;i<=n;i++)
	{
		nod[i]=new int[y[i]+2];
		cost[i]=new int[y[i]+2];
		y[i]=0;
	}

	for (i=1;i<=m;i++)
	{
		k=z[i].A;
		nod[k][++y[k]]=z[i].B;
		cost[k][y[k]]=z[i].C;
	}





	for (i=2;i<=n;i++)
		d[i]=inf;
	in=sf=iin=ssf=1;
	q[1]=1;
	while (iin<=ssf)
	{
		a=q[in];
		for (i=1;i<=y[a];i++)
		{
			k=nod[a][i];
			l=cost[a][i];
			if (d[k]>d[a]+l)
			{
				d[k]=d[a]+l;
				if (!viz[k])
				{
					sf=(sf+1)%50000;
					q[sf]=k;
					ssf++;
					viz[k]=1;
				}
			}

		}
		viz[a]=0;
		in++;
		iin++;
		in=in%50000;
	}


	for (a=2;a<=n;a++)
		for (i=1;i<=y[a];i++)
		{
			k=nod[a][i];
			l=cost[a][i];
			if (d[k]>d[a]+l)
			{
				printf("Ciclu negativ!\n");
				return 0;
			}
		 }
	for (i=2;i<=n;i++)
		if (d[i]!=inf)
			printf("%d ",d[i]);
		else
			printf("0 ");
	printf("\n");

	return 0;
}