# include <fstream>

using namespace std;

//standard Bellman Ford algorithm
//supposed to obtain 35p.

int x [ 250001 ], y [ 250001 ], c [ 250001 ], dist [ 50001 ];
const int inf = 2000000001;

int main(){

	ifstream f ( "bellmanford.in" );
	ofstream g ( "bellmanford.out" );

	int n, m, i, j;

	f >> n >> m;
	for ( i = 0; i < m; ++ i )
		f >> x [ i ] >> y [ i ] >> c [ i ];

	f . close ();

	for ( i = 2; i <= n; ++ i )
		dist [ i ] = inf;

	for ( i = 1; i < n; ++ i )
		for ( j = 0; j < m; ++ j )
			if ( dist [ y [ j ] ] > dist [ x [ j ] ] + c [ j ] )
				dist [ y [ j ] ] = dist [ x [ j ] ] + c [ j ];

	for ( j = 0; j < m; ++ j )
		if ( dist [ y [ j ] ] > dist [ x [ j ] ] + c [ j ] ){
			g << "Ciclu negativ!\n";
			g . close ();
			return 0;
		}

	for ( i = 2; i <= n; ++ i )
		g << dist [ i ] << ' ';
	g << '\n';
	g . close ();

	return 0;

}