#include <stdio.h>
#include <vector>
#include <queue>
#define N 50000
#define INF 250000000

struct muchie { int node, cost; };

std::vector <muchie> graf[N + 1];
std::queue <int> coada;
int cnt[N + 1], dis[N + 1];
bool inCoada[N + 1];
int n;

void init() {
    for ( int i = 1; i <= n; i ++ )
        inCoada[i] = false, dis[i] = INF;
}

bool eCicluNegativ( int node ) {
    init();

    coada.push( node );
    inCoada[node] = true;
    dis[node] = 0;
    cnt[node] ++;
    while ( !coada.empty() && cnt[coada.front()] < n ) {
        node = coada.front();
        coada.pop();
        inCoada[node] = false;
        for ( const muchie& vecin : graf[node] ) {
            if ( dis[vecin.node] > dis[node] + vecin.cost ) {
                dis[vecin.node] = dis[node] + vecin.cost;
                cnt[vecin.node] ++;
                if ( !inCoada[vecin.node] ) {
                    coada.push( vecin.node );
                    inCoada[vecin.node] = true;
                }
            }
        }
    }
    return !coada.empty();
}

int main() {
    FILE *fin, *fout;
    int m, x, y, c;

    fin = fopen( "bellmanford.in", "r" );
    fscanf( fin, "%d%d", &n, &m );
    for ( int i = 0; i < m; i ++ ) {
        fscanf( fin, "%d%d%d", &x, &y, &c );
        graf[x].push_back( { y, c } );
    }
    fclose( fin );

    fout = fopen( "bellmanford.out", "w" );
    if ( eCicluNegativ( 1 ) )
        fprintf( fout, "Ciclu negativ!" );
    else
        for ( int i = 2; i <= n; i ++ )
            fprintf( fout, "%d ", dis[i] );
    fputc( '\n', fout );
    fclose( fout );
    return 0;
}