#include<stdio.h>
#include<string.h>
#define inf 250000000
#define NMAX 50005
#define MMAX 250005
int a,b,c,i,j,w[MMAX],q,n,l,m,x[MMAX],y[MMAX],z[MMAX],p,d[NMAX];
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++)
	{
		w[i]=1;
		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++;
		q=0;
		while (j<l)
		{
			if (ss[j]=='-')
			{
				q=1;
				j++;
			}
			c=c*10+ss[j++]-48;
		}
		if (q)
			c=0-c;
	x[i]=a;
	y[i]=b;
	z[i]=c;

	}
	for (i=2;i<=n;i++)
		d[i]=inf;
	p=1;
	i=1;
	while (i<n&&p)
	{
		p=0;
		for (j=1;j<=m;++j)
		{
			a=x[j];
			b=y[j];
			c=z[j];
			if (b!=1)
			if (d[b]>d[a]+c&&w[j])
			{
				d[b]=d[a]+c;
				p=1;
				w[j]=0;
			}
		}
		i++;

	}
		for (j=1;j<=m;++j)
		{
			a=x[j];
			b=y[j];
			c=z[j];
			if (d[b]>d[a]+c)
			{
				printf("Ciclu negativ!");
				return 0;
			}
		}
	for (i=2;i<=n;i++)
		if (d[i]!=inf)
			printf("%d ",d[i]);
		else
			printf("0 ");
	printf("\n");
	return 0;
}