#include <bits/stdc++.h>
#define INFINIT 1000000000

std::vector< std::pair< int, int > >g[50001];
char inqueue[50001];
int d[50001], cl[50001];
std::queue< int >q;

int main() {
    FILE *fin, *fout;
    int n, m, i, ok, a, b, c, x, y, dxy;
    fin = fopen( "bellmanford.in", "r" );
    fout = fopen( "bellmanford.out", "w" );
    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d%d", &a, &b, &c );
        g[a].push_back( { c, b } );
    }
    for ( i = 2; i <= n; i++ )
        d[i] = INFINIT;
    q.push( 1 );
    ok = 1;
    while ( !q.empty() && ok ) {
        x = q.front();
        q.pop();
        inqueue[x] = 0;
        for ( i = 0; i < g[x].size(); i++ ) {
            y = g[x][i].second;
            dxy = g[x][i].first;
            if ( d[x] + dxy < d[y] ) {
                d[y] = d[x] + dxy;
                cl[y]++;
                if ( cl[y] >= n )
                    ok = 0;
                if ( inqueue[y] == 0 ) {
                    q.push( y );
                    inqueue[y] = 1;
                }
            }
        }
    }
    if ( ok == 0 ) {
        fprintf( fout, "Ciclu negativ!" );
    } else {
        for ( i = 2; i <= n; i++ )
            fprintf( fout, "%d ", d[i] );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}