#include <fstream>
#include <vector>
using namespace std;
ifstream cin( "bellmanford.in" );
ofstream cout( "bellmanford.out" );

int n, m, q[ 500001 ], prim, ultim;
int x, y, z, nr[ 50001 ], cost[ 50001 ];
vector<int> v[ 50001 ], c[ 50001 ];

inline int belf()
{
	int i;
	while ( prim <= ultim )
	{
		for ( i = 0; i < v[ q[ prim ] ].size(); i++ )
		{
			if ( cost[ v[ q[ prim ] ][ i ] ] > cost[ q[ prim ] ] + c[ q[ prim ] ][ i ] )
			{
				cost[ v[ q[ prim ] ][ i ] ] = cost[ q[ prim ] ] + c[ q[ prim ] ][ i ];
				q[ ++ultim ] = v[ q[ prim ] ][ i ];
				nr[ v[ q[ prim ] ][ i ] ]++;
			}
			if ( nr[ v[ q[ prim ] ][ i ] ] >= n ) return 0;
		}
		prim++;
	}
	return 1;
}

int main()
{
	int i, ok;
	cin >> n >> m;
	for ( i = 1; i <= m; i++ )
	{
		cin >> x >> y >> z;
		v[ x ].push_back( y );
		c[ x ].push_back( z );
	}
	for ( i = 2; i <= n; i++ )
		cost[ i ] = 2000000000;
	q[ 0 ] = 1;
	if ( !belf() ) cout << "Ciclu negativ!";
	else 
		for ( i = 2; i <= n; i++ )
			cout << cost[ i ] << " ";
}