#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[50010][50010];
	
int NR[50010];
int start, n, m;
int C[50010];
int nrpus[50010], cmin[50010];

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;
	C[1]=1;
	inc=1; sf=1;
	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]=A[x][y].x; nrpus[A[x][y].x]++;
				if(nrpus[A[x][y].x]==n)//nu exista solutie
				{ 
					fout<<"Ciclu negativ!"<<'\n';
					return 0;
				}
			}
	}
	for(i=2;i<=n;i++)
		fout<<cmin[i]<<' ';
	fout<<'\n';
}