#include <fstream>

using namespace std;

const char InFile[]="bellmanford.in";
const char OutFile[]="bellmanford.out";
const int MaxM=250010;
const int MaxN=50010;
const int INF=1<<30;

ifstream fin(InFile);
ofstream fout(OutFile);

struct edge{int x,y,cost;};

edge uv[MaxM];
int N,M,prev[MaxN],dist[MaxN];

bool bellmanford()
{
	for(register int i=1;i<=N;++i)
	{
		dist[i]=INF;
		prev[i]=0;
	}
	dist[1]=0;
	
	for(register int i=1;i<=N-1;++i)
	{
		for(register int j=0;j<M;++j)
		{
			if(uv[j].cost!=INF && dist[uv[j].x]!=INF)
			{
				if(uv[j].cost+dist[uv[j].x]<dist[uv[j].y])
				{
					dist[uv[j].y]=uv[j].cost+dist[uv[j].x];
					prev[uv[j].y]=uv[j].x;
				}
			}
		}
	}

	for(register int j=0;j<M;++j)
	{
		if(uv[j].cost!=INF && dist[uv[j].x]!=INF)
		{
			if(uv[j].cost+dist[uv[j].x]<dist[uv[j].y])
			{
				return false;
			}
		}
	}
	return true;
}

int main()
{
	fin>>N>>M;
	for(register int i=0;i<M;++i)
	{
		fin>>uv[i].x>>uv[i].y>>uv[i].cost;
	}
	fin.close();

	if(bellmanford())
	{
		for(register int i=2;i<=N;++i)
		{
			fout<<dist[i]<<" ";
		}
	}
	else
	{
		fout<<"Ciclu negativ!";
	}
	fout.close();
	return 0;
}