#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 ) {}
};

const int nmax = 5 * 1e4;
const int inf = (1 << 30);

int n;
int d[nmax + 1], modif[nmax + 1];
vector< muchie > g[nmax + 1];
bool f[nmax + 1];

queue< int > q;

bool bellman_ford() {
    q.push( 1 );
    f[ 1 ] = modif[ 1 ] = 1;
    d[ 1 ] = 0;

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        f[ x ] = 0;

        for (auto i : g[ x ]) {
            if (d[ i.x ] > d[ x ] + i.c) {
                d[ i.x ] = d[ x ] + i.c;

                if (f[ i.x ] == 0) {
                    ++ modif[ i.x ];

                    if (modif[ i.x ] >= n) {
                        return 1;
                    }

                    f[ i.x ] = 1;
                    q.push( i.x );
                }
            }
        }
    }
    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;
}