#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define INF 1<<17
using namespace std;
const char iname[] = "bellmanford.in";
const char oname[] = "bellmanford.out";
ifstream fin(iname);
ofstream fout(oname);
int N , M , i , j , x;
int cost[ 50004 ] , ord[ 50004 ];
struct nod{
	int x , c;
}var;
vector < nod > v[ 50004 ];
queue < int > Q;
int Bell()
{
	vector < nod > :: iterator it;
	while( !Q.empty() )
	{
		x = Q.front();
		Q.pop();
		for ( it = v[ x ].begin(); it != v[ x ].end(); ++it )
		{
			if ( cost[ x ] + it -> c < cost[ it -> x ] )
			{
				cost[ it -> x ] = cost[ x ] + it -> c;
				Q.push( it -> x );
				ord[ it -> x ] = ord[ x ] + 1;
			}
			if ( ord[ it -> x ] > N )
				return 0;
		}
	}
	return 1;
}
int main()
{
	fin >> N >> M;
	for ( i = 1; i <= N; ++i ) cost[ i ] = INF;
	for ( i = 1; i <= M; ++i )
	{
		fin >> x >> var.x >> var.c;
		v[ x ].push_back( var );
	}
	cost[ 1 ] = 0; Q.push( 1 );
	if( Bell() )
	{
		for ( i = 2; i <= N; ++i ) if ( cost[ i ] != INF ) fout << cost[ i ] << ' ';
		fout << '\n';
		return 0;
	}
	else
		fout << "Ciclu negativ!" << '\n';
	return 0;
}