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

const int NMAX  = 50001;
const int INFI  = 0X3F3F3F3;

struct Muchie{
    int nod, cost;
};

vector < Muchie > V[ NMAX ];

int D[ NMAX ],
    Cnt[ NMAX ],
    InQ[ NMAX ];

bool BellmanFord( int start, int n ) {

    int i, j, k, nod, fiu;
    queue < int > Q;

    for ( i = 0; i <= n; ++i ) {
        D[ i ] = INFI;
    }

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

    while ( !Q.empty() ) {
        nod = Q.front();
        Q.pop();
        InQ[ nod ] = 0;
        if ( Cnt[ nod ] > n ) {
            return false;
        }
        Cnt[ nod ]++;
        for ( i = 0; i < V[ nod ].size(); ++i ) {
            fiu = V[ nod ][ i ].nod;
            int cost = V[ nod ][ i ].cost;
            if ( D[ fiu ] > D[ nod ] + cost ) {
                D[ fiu ] = D[ nod ] + cost;
                if ( !InQ[ fiu ] ) {
                    InQ[ fiu ] = 1;
                    Q.push( fiu );
                }
            }
        }
    }

    return true;

}

int main () {

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

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

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

    if ( !BellmanFord( 1, n ) ) {
        printf( "Cicluri negative!" );
    } else {
        for ( i = 2; i <= n; ++i ) {
            printf( "%d ", D[ i ] );
        }
    }

    return 0;
}