#include<stdio.h>
#define nmax 50005 
#define inf 2000000000
int d[nmax], vz[nmax], n, m, i;
struct elem
{	int v, c;
	elem *nxt;
};
elem *a[nmax], *q;

void read()
{	int x, y, c, i;
	scanf("%d%d", &n, &m);
	for(i=1; i<=m; i++)
	{	scanf("%d%d%d", &x, &y, &c);
		q=new elem;
		q->c=c; q->v=y;
		q->nxt=a[x]; a[x]=q;
	}		
}

int solve()
{	int cd[10*nmax], p, u, i;
	p=u=1;
	for(i=2; i<=n; i++)
		d[i]=inf;
	cd[p]=1; vz[p]=1;
	while(p<=u)	
	{	q=a[cd[p]];
		while(q)
		{	if(q->c+d[cd[p]]<d[q->v])
			{	if(vz[q->v]==0)
				{	u++; cd[u]=q->v; vz[q->v]=1;
				}
			/*	else
					if((d[q->v] + d[cd[p]] + q->c)<0)
						return -1;*/
				d[q->v]=q->c+d[cd[p]];
			}
			q=q->nxt;
		}
		vz[cd[p]]=0;
		p++;
	}
	for(i=1; i<=n; i++)
	{	q=a[i];
		while(q)
		{	if(d[q->v]>d[i]+q->c)
				return -1;
			q=q->nxt;
		}
	}
	for(i=1; i<=n; i++)
		if(d[i]==inf)
			d[i]=0;
	return 0;
}

int main()
{
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);
	read();
	
	if(	solve()==-1 )
		printf("Ciclu negativ!\n");
	else
	{	for(i=2; i<=n; i++)
			printf("%d ", d[i]);
	}	
	return 0;
	
}