#include<fstream>
#include <fstream>
#define INF 1000000000

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

void citire();
void bellman_ford();

struct vfc
{
	int x;
	double c;
} A[5010][5010];
	
int NR[5010];
int start, n, m;
int C[5010];
int nrpus[5010], cmin[5010];

int main ()
{
	citire();
	bellman_ford();
	return 0;
}

void citire()
{
	int i, a, b, c;
	fin>>n>>m; start=1;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b>>c;
		NR[a]++;
		A[a][NR[a]].x=b;
		A[a][NR[a]].c=c;
	}
}

void bellman_ford()
{
	int i, inc, sf, ok=0;
	int x, y;
	for(i=1;i<=n;i++)
		cmin[i]=INF;
	cmin[start]=0;
	for(i=1;i<=n;i++)
	{
		C[i]=i; nrpus[i]=1; 
	}
	inc=1; sf=n;
	while(inc<=sf)
	{
		x=C[inc]; inc++;
		for(y=1;y<=NR[x];y++)
			if(cmin[A[x][y].x]>cmin[x]+A[x][y].c)
			{
				cmin[A[x][y].x]=cmin[x]+A[x][y].c;
				sf++; C[sf]=y; nrpus[y]++;
				if(nrpus[y]>=n)//nu exista solutie
				{ ok=1;	break; }
			}
		if(ok==1)
			break;
	}
	if(ok==1)
		 fout<<"Ciclu negativ!"<<'\n';
	else
	{
		for(i=2;i<=n;i++)
			fout<<cmin[i]<<' ';
		fout<<'\n';
	}
}