#include <cstdio>
#include <queue>
#include <vector>

using namespace std ;

const int NMAX = 50001 ;
const int MMAX = 250001;
const int INF = 1<<30;

struct NOD { int nr , cost ; } ;

vector<NOD> mat[NMAX];
bool f[NMAX];
int nr[NMAX];
int d[NMAX];
queue<int> q ;

int main ( )
{
	
	freopen ( "bellmanford.in", "r", stdin ) ;
	freopen ( "bellmanford.out", "w", stdout ) ;
	
	int N , M , i , x , y , cost ;
	
	scanf ( "%d%d", & N , & M ) ;
	
	for ( i = 1; i <= M ; ++ i )
	{
		scanf ( "%d%d%d", & x , & y , & cost ) ;
		mat[x].push_back ( (NOD){y,cost} ) ;
	}
	
	for ( i = 1 ; i <= N ; ++ i )
	{
		d[i] = INF ;
	}
	
	q.push ( 1 ) ;
	d[1] = 0 ;
	
	while ( ! q.empty ( ) )
	{
		x = q.front () ;
		//printf ( "%d \n" , x ) ;
		f[x] = false ;
		q.pop () ;
		for ( size_t i = 0 ; i < mat[x].size () ; ++ i )
		{
			y = mat[x][i].nr ;
			if ( d[x] + mat[x][i].cost < d[y] )
			{
				d[y] = d[x] + mat[x][i].cost ;
				if ( ! f[y] )
				{
					q.push ( y ) ;
					f[y] = true ;
					++ nr[y] ;
					if ( nr[y] == N )
					{
						printf ( "Ciclu negativ!" , y ) ;
						return 0 ;
					}
				}
			}
		}
	}
	
	for ( i = 2 ; i <= N ; ++ i ) 
	{
		printf ( "%d " , d[i] ) ;
	}
	
	return 0 ;
}