#include<fstream>
#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 ], modif[ nmax + 1 ];
graf g[ nmax + 1 ];
bool f[ nmax + 1 ];

int q[ nmax + 1 ];

bool bellman_ford() {
    int first = 0, last = -1;
    q[ ++ last ] = 1;
    f[ 1 ] = 1;
    d[ 1 ] = 0;

    while ( first <= last) {
        int i = q[ first ++ ];

        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);
                ++ modif[ it -> x ];
                if ( modif[ it -> x ] >= n ) {
                    return 1;
                }
                if ( f[ it -> x ] == 0 ) {
                    q[ ++ last ] = it -> x;
                    f[ it -> x ] = 1;
                }
            }
        }
        f[ i ] = 0;
    }
    return 0;
}
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;
    if ( 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;
}