#include<stdio.h>
#include<vector>
using namespace std;
FILE*f=fopen("bellmanford.in","r");
FILE*g=fopen("bellmanford.out","w");
int n,m,x,y,c,nr,d[50001];
vector <pair<int,int> > v[50001];
struct muchii
{
	int x,y,c;
}w[250001];
int main()
{
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&x,&y,&c);
		v[i].push_back (make_pair(x,y));
		w[++nr].x=x;
		w[nr].y=y;
		w[nr].c=c;
	}
	
	
	for(int i=2;i<=n;++i)
		d[i]=2000000000;
	
	int ok=1;
	int o;
	for(o=1;ok&&o<n;++o)
	{
		ok=0;
		for(int i=1;i<=m;++i)
		{
			if(d[w[i].y]>d[w[i].x]+w[i].c)
			{
				d[w[i].y]=d[w[i].x]+w[i].c;
				ok=1;
			}
		}
	
	}
	
	if(o==n)
		fprintf(g,"Ciclu negativ!");
	else
		for(int i=2;i<=n;++i)
			fprintf(g,"%d ",d[i]);
	
	
	fclose(g);
	fclose(f);
	return 0;
}