#include <cstdio>

using namespace std;

const int Nmax = 50000;
const int Mmax = 250000;
const int Inf = 0x3F3F3F3F;
const int NIL = -1;

struct __attribute__((packed)) Edge {
    unsigned short v;
    short cost : 11;
    int next : 20;
};

unsigned long long inQueue[(Nmax >> 6) + 1];

Edge l[Mmax];
int adj[Nmax];
unsigned short n;

unsigned short Q[Nmax], qStart, qEnd;

unsigned short used[Nmax];

int D[Nmax];

inline void toggleInQueue( const unsigned short &pos ) {
    inQueue[ pos >> 6 ] ^= (1ULL << ( pos & 63 ));
}

inline bool checkInQueue( const unsigned short &pos ) {
    return inQueue[ pos >> 6 ] & (1ULL << ( pos & 63 ));
}

inline unsigned short qPop() {
    unsigned short key = Q[ qStart++ ];

    if ( qStart == n ) {
        qStart = 0;
    }
    return key;
}

inline void qPush( const unsigned short &u ) {
    Q[ qEnd++ ] = u;

    if ( qEnd == n ) {
        qEnd = 0;
    }
}

inline void addEdge( const int &u, const unsigned short &v, const short &cost, const int &pos ) {
    l[pos].v = v;
    l[pos].cost = cost;
    l[pos].next = adj[u];
    adj[u] = pos;
}

int main(void) {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    unsigned m;
    unsigned short u, v;
    bool negativeCycle;
    short cost;

    scanf("%hu%u", &n, &m);

    for ( unsigned short i = 0; i < n; i++ ) {
        adj[i] = NIL;
        D[i] = Inf;
    }

    for ( unsigned i = 0; i < m; i++ ) {
        scanf( "%hu%hu%hd", &u, &v, &cost );
        addEdge( u - 1, v - 1, cost, i );
    }

    fclose(stdin);

    qPush( 0 );
    toggleInQueue( 0 );
    D[0] = 0;
    negativeCycle = 0;
    do {
        u = qPop();

        toggleInQueue( u );

        int i = adj[u];

        while ( i != NIL && !negativeCycle ) {

            v = l[i].v;
            int c = D[u] + l[i].cost;

            if ( D[v] > c ) {
                D[v] = c;
                if ( !checkInQueue( v ) ) {
                    if ( used[v] > n ) {
                        negativeCycle = 1;
                    } else {
                        used[v]++;
                        toggleInQueue( v );
                        qPush( v );
                    }
                }
            }
            i = l[i].next;
        }

    } while ( qStart != qEnd && !negativeCycle );

    if ( negativeCycle ) {
        puts("Ciclu negativ!");
    } else {
        for ( unsigned short i = 1; i < n; i++ ) {
            printf( "%d ", D[i] );
        }
    }
    fclose(stdout);
    return 0;
}