#include<fstream>
#include<vector>

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 ];

int mini_bellman_ford() {
    int better = 0;
    for( int i = 1; i <= n; ++ i ) {
        if ( d[ i ] != inf ) {
            for( graf::iterator it = g[ i ].begin(); it != g[ i ].end(); ++ it ) {
                if ( d[ it -> x ] > d[ i ] + (it -> c) ) {
                    ++ better;
                    d[ it -> x ] = d[ i ] + (it -> c);
                }
            }
        }
    }
    return better;
}
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; ++ i ) {
        mini_bellman_ford();
    }

    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;
}