#include <vector>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
  
#define MAX_SIZE 50005
#define get_max( a,b) ((a)>(b)?(a):(b))
#define mk make_pair
#define INF 0x3f3f3f3f
  
using namespace std;
  
typedef vector < pair < int,int > > ::iterator vii;
  
ifstream in ( "bellmanford.in" );
ofstream out ( "bellmanford.out" );
  
vector <  pair < int  ,int > > G[MAX_SIZE] ;
int N , M , Cost[MAX_SIZE] , Nr_Vis[MAX_SIZE];
queue < int >  Q ;
bool InQueue[MAX_SIZE] , NegativCycle;  


void BellmanFord ( void )
{
    memset ( Cost , INF , sizeof ( Cost ) );
    Cost[1] = 0 ;
    Q.push( 1 );
	for ( ; !Q.empty() ; )
    {
        int node = Q.front();Q.pop();
		InQueue[node] = false;
        for( vii it = G[node].begin();  it != G[node].end() ; ++it )
            if ( Cost[it->first] > Cost[node] + it->second )
            {
                Cost[it->first] = Cost[node] + it->second;
                if( !InQueue[it->first] )
				{
					++Nr_Vis[it->first];
					Q.push(it->first);
				}
				if ( Nr_Vis[it->first] >= N )
				{
					NegativCycle = true ;
					return ;
				}
            }
    }
}
  
  
int main ( void )
{
    int i , j , x , y , c ;
    in >> N >> M ;
    for ( i = 1 ; i <= M ; ++i )
    {
        in >> x >> y >> c ;
        G[x].push_back(mk(y,c));
    }
    BellmanFord();
	if ( !NegativCycle )
    for ( i = 2 ; i <= N ; ++i )
        out << Cost[i]  << " ";
	else out << "Ciclu negativ!";
    in.close();
    out.close();
    return 0 ;
}