//Bellman - Ford bc

#include <stdio.h>
#define nmax 50001
#define mmax 250001

struct muchie {int x,y,cost;} a[mmax];
int c[nmax],n,m;
long long nr;

int costneg()
{
    for(int i=1;i<=m;i++)
        if(c[a[i].x]+a[i].cost<c[a[i].y])
            return 1;
    return 0;
}

int main()
{
	int i,ok=0;
	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",&a[i].x,&a[i].y,&a[i].cost);
		if(a[i].x==1)
			c[a[i].y]=a[i].cost;
	}
	for(i=2;i<=n;i++)
		if(c[i]==0)
			c[i]=mmax;
	while(ok==0)
	{
		ok=1;
		nr++;
		if(nr>(long long)n*m) break;
		for(int i=1;i<=m;i++)
			if(c[a[i].y]>c[a[i].x]+a[i].cost)
			{
				c[a[i].y]=c[a[i].x]+a[i].cost;
				ok=0;
			}
	}
	if(costneg())
        printf("Ciclu negativ!\n");
    else
	for(i=2;i<=n;i++)
	{
		if(c[i]==mmax)
			printf("0 ");
		else
			printf("%d ",c[i]);
	}
	return 0;
}