#include<fstream>
#include<queue>
#include<vector>
#include<cstring>

using namespace std;

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

struct muchie{
    int x, c;

    muchie() {}
    muchie( int _x, int _c ) : x( _x ), c( _c ) {}
};
typedef vector< muchie > graf;

const int nmax = 5 * 1e4;
const int inf = (1 << 30);
int n;
int d[ nmax + 1 ];
graf g[ nmax + 1 ];
bool f[ nmax + 1 ];

queue< int > q;

int mini_bellman_ford() {
    int better = 0;
    memset( f, 0, sizeof( f ) );

    while ( q.size() ) q.pop();
    q.push( 1 );
    f[ 1 ] = 1;

    while ( !q.empty() ) {
        int i = q.front();
        q.pop();
        ++ better;

        for( graf::iterator it = g[ i ].begin(); it != g[ i ].end(); ++ it ) {
            if ( d[ it -> x ] > d[ i ] + (it -> c) ) {
                d[ it -> x ] = d[ i ] + (it -> c);

                if ( f[ it -> x ] == 0 ) {
                    q.push( it -> x );
                    f[ it -> x ] = 1;
                }
            }
        }

        f[ i ] = 0;
    }
    return better - 1;
}
int main() {
    int m;
    fin >> n >> m;
    for( int i = 0; i < m; ++ i ) {
        int x, y, c;
        fin >> x >> y >> c;
        g[ x ].push_back( muchie( y, c ) );
    }
    for( int i = 1; i <= n; ++ i ) {
        d[ i ] = inf;
    }
    d[ 1 ] = 0;
    for( int i = 1; i < n && mini_bellman_ford(); ++ i ) {
    }

    if ( mini_bellman_ford() ) {
        fout << "Ciclu negativ!\n";
    } else {
        for( int i = 2; i <= n; ++ i ) {
            fout << d[ i ] << " ";
        }
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}