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

#define INF ( 1<<30 )
#define MAXN 50001
#define MAXM 250001
#define pb push_back
#define sz size()

struct muchie {

    int x, y, c;
};

int n, m, d[ MAXN ], f[ MAXN ];
queue <int> q;
muchie a[ MAXM ];
vector <int> v[ MAXN ];

int check() {

    int i;

    for( i = 1; i <= m; ++i )
        if( d[ a[ i ].x ] + a[ i ].c < d[ a[ i ].y ] )
            return 1;

    return 0;
}

void init() {

    int i;

    for( i = 1; i <= n; ++i )
        d[ i ] = INF;
    d[ 1 ] = 0;
}

void bford() {

    int i, nod, poz;
    unsigned int I;

    f[ 1 ] = 1;
    for( i = 1, q.push( 1 ); !q.empty() && 1LL*i <= 1LL*n*m; q.pop(), ++i ) {

        nod = q.front();
        f[ nod ] = 1;
        for( I = 0; I < v[ nod ].sz; ++I ) {

            poz = v[ nod ][ I ];
            if( d[ nod ] + a[ poz ].c < d[ a[ poz ].y ] ) {

                d[ a[ poz ].y ] = d[ nod ] + a[ poz ].c;
                if( !f[ a[ poz ].y ] ) {

                    q.push( a[ poz ].y );
                    f[ a[ poz ].y ] = 1;
                }
            }
        }
    }
}

int main() {

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

    int i;

    scanf( "%d %d", &n, &m );
    for( i = 1; i <= m; ++i ) {

        scanf( "%d %d %d", &a[ i ].x, &a[ i ].y, &a[ i ].c );
        v[ a[ i ].x ].pb( i );
    }

    init();
    bford();

    if( check() ) {

        printf( "Ciclu negativ!" );
        return 0;
    }

    for( i = 2; i <= n; ++i )
        printf( "%d ", d[ i ] );

    return 0;
}