#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

#define inf 0x3f3f3f3f
#define PB push_back
#define MP make_pair
#define nmax 50001

using namespace std;

queue < int > Q ;
vector < pair < int , int  > > A[ nmax ] ;
int N , M , cost[ nmax ] , vizitat [ nmax ] ;

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

int bellman( )
{
    for( int i = 1 ; i <= N ; i++ )
    cost[ i ] = inf ;

    vizitat[ 1 ] = 1;
    cost [ 1 ] = 0;
    Q.push( 1 ) ;

    while( ! Q.empty())
    {
        int nod = Q.front();
        Q.pop();

        for( unsigned int i = 0 ; i < A[ nod ].size() ; i++ )
        {
            int nod2 = A[ nod ][ i ].first ;
            int cost2 = A[ nod ][ i ].second ;

            if( cost[ nod2 ] <= cost[ nod ] + cost2 )
            continue ;

            vizitat[ nod2] ++ ;

            if( vizitat[ nod2 ] > N )
            {
                g<<"Cliclu negativ!";

                return 0 ;

            }

            cost[ nod2 ] = cost[ nod ] + cost2 ;
             Q.push( nod2 ) ;
        }

    }

    return 1 ;
}







int main()
{
    f >> N >> M ;

    for( int i = 1 ; i <= M ; i++ )
    {
        int x , y , c ;

        f >> x >> y >> c ;

        A[ x ].PB ( MP ( y , c ));

    }

    if(bellman ( ))
    for( int i = 2 ; i <= N ; i++ )

        g<< cost[ i ] <<" ";

        f.close( );
        g.close( );


return 0;
}