# include <fstream>
# include <vector>
# include <queue>
using namespace std ;

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

const int nMax = 50003 ;
int n , m , cost [ nMax ] , timesinq [ nMax ] ;
vector < pair < int , int > > a [ nMax ] ;
queue < int > q ;
bool inq [ nMax ] ;

void scan (  )
{
    in >> n >> m ;

    for ( int i = 1 , a1 , b , c ; i <= m ; ++ i )
    {
        in >> a1 >> b >> c ;

        a [ a1 ] . push_back ( make_pair ( b , c ) ) ;
        //a [ b ] . push_back ( make_pair ( a1 , c ) ) ;
    }
}

bool bf (  )
{
    for ( int i = 2 ; i <= n ; ++ i )
    {
        cost [ i ] = 2000000000 ;
    }

    q . push ( 1 ) ;
    inq [ 1 ] = true ;
    timesinq [ 1 ] = 1 ;

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


        //out << " Am scos : " << nod << '\n' ;
        //out << " Am adaugat : " ;

        for ( size_t i = 0 ; i < a [ nod ] . size (  ) ; ++ i )
        {
            if ( a [ nod ] [ i ] . second  + cost [ nod ] < cost [ a [ nod ] [ i ] . first ] )
            {
                ++ timesinq [ a [ nod ] [ i ] . first ] ;
                    //out << a [ nod ] [ i ] . first << ' ' ;
                    if ( timesinq [ a [ nod ] [ i ] . first ] == n )
                    {
                        return true ;
                    }
                cost [ a [ nod ] [ i ] . first ] = a [ nod ] [ i ] . second  + cost [ nod ] ;
                if ( ! inq [ a [ nod ] [ i ] . first ] )
                {
                    inq [ a [ nod ] [ i ] . first ] = true ;

                    q . push ( a [ nod ] [ i ] . first ) ;
                }
            }
        }

        //out << "\n\n\n" ;
        inq [ nod ] = false ;
    }

    return false ;
}

void runProgram (  )
{
    scan (  ) ;

    if ( bf (  ) )
    {
        out << "Ciclu negativ!\n" ;

        return ;
    }

    for ( int i = 2 ; i <= n ; ++ i )
    {
        out << cost [ i ] << ' ' ;
    }
    out << '\n' ;
}

int main (  )
{
    runProgram (  ) ;

    return 0 ;
}