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

using namespace std;
const int nmax = 5e4;
const int oo = 1e9;
const int ciclu = 1;

struct Edge { int to; int cost; };
queue < int > q;
vector < Edge > g[nmax + 1];

bool inq[nmax + 1];
int cnt[nmax + 1];
int dist[nmax + 1];

int n;

int bellman ( int node = 1 ) {
    q.push ( node );
    dist[node] = 0;

    while ( ! q.empty () ) {
        int node = q.front ();
        q.pop ();
        inq[node] = 0;
        for ( Edge &x: g[node] )
            if ( dist[node] + x.cost < dist[x.to] ) {
                dist[x.to] = dist[node] + x.cost;
                cnt[x.to]++;
                if ( cnt[x.to] > n )
                    return ciclu;

                if ( inq[x.to] == false ) {
                    q.push ( x.to );
                    inq[x.to] = true;
                }
            }
    }
    return !ciclu;
}

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

int main() {
    int m, x, y, c;
    fin >> n >> m;

    for ( int i = 1; i <= n; i++ )
        dist[i] = oo;

    for ( int i = 0; i < m; i++ ) {
        fin >> x >> y >> c;
        g[x].push_back ( { y, c } );
    }

    if ( bellman () == ciclu )
        fout << "Ciclu negativ!\n";
    else {
        for ( int i = 2; i <= n; i++ )
            fout << ( dist[i] == oo ? 0 : dist[i] ) << ' ';
        fout << '\n';
    }

    return 0;
}