#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define NMAX 50005
#define INFI 0x3f3f3f3f

vector < pair < int, int > > V[ NMAX ];
queue < int > Q;

int OK;
int D[ NMAX ];
int inQ[ NMAX ];
int Count[ NMAX ];

void Bellman ( int start, int n ) {

    int i, j, x, y, c;
    pair < int, int > nod;
    vector < pair < int, int > > :: iterator it;

    while ( !Q.empty() ) Q.pop();
    for ( i = 1; i <= n; ++i ) {
        D[ i ] = INFI;
        Count[ i ] = 0;
    }

    D[ start ] = 0;
    Q.push( start );

    while ( !Q.empty() ) {
        x = Q.front();
        inQ[ x ] = 0;
        Q.pop();
        if ( Count[ x ] > n ) {
            OK = 1;
            return ;
        } else {
            Count[ x ]++;
        }
        for ( it = V[ x ].begin(); it != V[ x ].end(); ++it ) {
            nod = *it; y = nod.first; c = nod.second;
            if ( D[ y ] > D[ x ] + c ) {
                D[ y ] = D[ x ] + c;
                if ( !inQ[ y ] ) {
                    Q.push( y );
                    inQ[ y ] = 1;
                }
            }

        }
    }


}

int main () {

    freopen( "bellmanford.in", "r", stdin );
    freopen( "bellmanford.out", "w", stdout );

    int n, m, i, j, x, y, c;

    scanf( "%d%d",&n,&m );

    while ( m-- ) {
        scanf( "%d%d%d",&x,&y,&c );
        V[ x ].push_back( { y, c } );
    }

    Bellman( 1, n );

    if ( OK ) {
        printf( "Ciclu negativ!\n" );
    } else {
        for ( i = 2; i <= n; ++i ) printf( "%d ",D[ i ] );
    }

    return 0;

}