#include <cstdio>
#include <cstdlib>
#include <cctype>

using namespace std;

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

char buffer[Bsize];
int ptr = Bsize;

inline char GetChar() {
    if ( ptr == Bsize ) {
        fread(buffer, 1, Bsize, stdin);
        ptr = 0;
    }
    return buffer[ ptr++ ];
}

template <class T>
inline void read(T &q) {
    bool sign = 0;
    char c;

    do {
        c = GetChar();
        sign |= ( c == '-' );
    } while ( !isdigit(c) );

    q = 0;

    do {
        q = (10 * q) + (c - '0');
        c = GetChar();
    } while ( isdigit(c) );

    q ^= ((q ^ -q) & -sign);
}

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

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;
    short cost;

    read(n);
    read(m);

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

    for ( unsigned i = 0; i < m; i++ ) {
        read(u);
        read(v);
        read(cost);
        addEdge( u - 1, v - 1, cost, i );
    }

    fclose(stdin);

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

        toggleInQueue( u );

        for ( int i = adj[u]; i != NIL; i = l[i].next ) {

            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 ) {
                        puts("Ciclu negativ!");
                        fclose(stdout);
                        exit(0); // te-ai dus
                    } else {
                        used[v]++;
                        toggleInQueue( v );
                        qPush( v );
                    }
                }
            }
        }
    } while ( qStart != qEnd );

    for ( unsigned short i = 1; i < n; i++ ) {
        printf( "%d ", D[i] );
    }
    fclose(stdout);
    return 0;
}