#include<stdio.h>
#define Nmax  50010
#define Mmax 250010
#define infinit 2000000000
int n,m,d[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,j,u,v,c;
	for(i=2;i<=n;i++)
		d[i]=infinit;
	for(i=1;i<n;i++)
		for(j=0;j<m;j++)
		{
			u=e[j].x;
			v=e[j].y;
			c=e[j].cost;
			if(d[u]+c<d[v] && d[u]!=infinit)
				d[v]=d[u]+c;
		}
	for(i=0;i<m;i++)
	{
		u=e[i].x;
		v=e[i].y;
		c=e[i].cost;
		if(d[u]+c<d[v])
			return 1;
	}
	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;
}