#include<stdio.h>
#include<queue>
#define Nmax 50010
#define Inf 1<<30
using namespace std;

int n,m,i,cst,x,y,best[Nmax],viz[Nmax],cnt[Nmax],ciclu,nod;
struct graf {int inf,cost; graf *adr;} *v[Nmax];
queue<int> Q;

void add(int i, int j, int cst)
{
	graf *c;
	c=new graf;
	
	c->inf=j;
	c->cost=cst;
	c->adr=v[i];
	v[i]=c;
}

int main()
{
	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",&x,&y,&cst);
		add(x,y,cst);
	}
		
	for(i=2;i<=n;i++)
		best[i]=Inf;
	
	Q.push(1); cnt[1]=1;
	graf *c;
	
	while(!Q.empty() && !ciclu)
	{
		nod=Q.front();
		Q.pop();
		viz[nod]=0;
		
		for(c=v[nod];c;c=c->adr)
		{
			if(best[c->inf] > best[nod]+c->cost)
			{
				best[c->inf]=best[nod]+c->cost;
				cnt[c->inf]++; 
				if(cnt[c->inf]==n) {ciclu=1; break;}
				if(!viz[c->inf]) {Q.push(c->inf); viz[c->inf]=1;}
			}
		}
	}
	if(ciclu) {printf("Ciclu negativ!"); return 0;}
	
	for(i=2;i<=n;i++)
		printf("%d ",best[i]);
return 0;
}