#include<stdio.h>
#define Nmax  50010
#define Mmax 250010
#define infinit 2000000000
int n,m,d[Nmax],viz[Nmax],nr[Nmax];
struct nod
{
	int inf,cost;
	nod *urm;
}*a[Nmax];
struct edge
{
	int x,y,cost;
}e[Mmax];
int BF()
{
	d[1]=0;
	int i;
	for(i=2;i<=n;i++)
		d[i]=infinit;
	int c[10*Nmax];
	c[0]=1;
	int p,u;
	p=0;u=0;
	nod *q;
	while(p<=u)
	{
		for(q=a[c[p]];q!=NULL;q=q->urm)
		{
			if(d[c[p]]+q->cost<d[q->inf])
			{
				d[q->inf]=d[c[p]]+q->cost;
				if(viz[q->inf]==0)
				{	c[++u]=q->inf;
					viz[q->inf]=1;
					nr[q->inf]++;
				}
			}
			if(nr[q->inf]==n)
				return 1;
		}
		viz[c[p]]=0;
		p++;
	}
	return 0;
}
int main()
{
	int i;
	nod *p;
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++)
	{
		scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].cost);
		p=new nod;
		p->inf=e[i].y;
		p->cost=e[i].cost;
		p->urm=a[e[i].x];
		a[e[i].x]=p;
	}
	if(BF()==1)
		printf("Ciclu negativ!");
	else
		for(i=2;i<=n;i++)
			printf("%d ",d[i]);
	return 0;
}