#include<stdio.h>
#define infi 1<<30
int viz[50005],cost[50005],n,m,x,y,z,i,k,s[50010];
struct nod
{
	int inf;
	int cst;
	nod *adr;
};
nod *l[250005],*c,*p;
int main()
{
	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",&x,&y,&z);
		c=new nod;
		c->inf=y;
		c->cst=z;
		c->adr=l[x];
		l[x]=c;
	}
	for(i=0;i<=n;i++)
		cost[i]=infi;
	k=1;s[k]=1;viz[k]++;cost[k]=0;
	for(i=1;i<=k;i++)
	{
		p=l[s[i]];
		while(p)
		{
			if(p->cst+cost[s[i]]<cost[p->inf])
			{
				cost[p->inf]=p->cst+cost[s[i]];
			//	if(!viz[p->inf])
				s[++k]=p->inf;
				viz[p->inf]++;
				if(viz[p->inf]>=n){printf("Ciclu negativ!");return 0;}
			}
			p=p->adr;
		}
	}
	for(i=2;i<=n;i++)
		printf("%d ",cost[i]);
	return 0;
}