#include<stdio.h>
#include<string.h>
#define NMAX 50002
#define MMAX 250001
#define inf 20000000
int *nod[NMAX],*cost[NMAX];
int qq,iin,ssf,in,sf,viz[NMAX],d[NMAX],y[MMAX],q[NMAX],i,j,n,m,k,l,a,s,b,c;
struct kkt
{
	int A,B,C;
};
kkt z[MMAX];
char ss[32];
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d%c",&n,&m,&c);
	for (i=1;i<=m;i++)
	{
		fgets(ss,32,stdin);
		l=strlen(ss)-1;
		a=b=c=j=0;
		while (ss[j]!=' ')
			a=a*10+ss[j++]-48;

		j++;
		while (ss[j]!=' ')
			b=b*10+ss[j++]-48;

		j++;
		qq=0;
		while (j<l)
		{
			if (ss[j]=='-')
			{
				qq=1;
				j++;
			}
			c=c*10+ss[j++]-48;
		}
		if (qq)
			c=0-c;
		z[i].A=a;
		z[i].B=b;
		z[i].C=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&&ssf<MMAX+MMAX)
	{
		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)%(n+1);
					q[sf]=k;
					ssf++;
					viz[k]=1;
				}
			}

		}
		viz[a]=0;
		in++;
		iin++;
		in=in%(n+1);
	}


	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");
//	printf("Ciclu negativ!\n");

	return 0;
}