#include <vector>
#include <cstdio>
#include <queue>
#include <cstring>
#define NMAX 50009
#define oo (1<<30)
#define n first
#define c second
using namespace std;

typedef pair<int, int> edge;

int N, M, d[ NMAX ], used[ NMAX ];
bool inQ[NMAX];
vector< edge > G[NMAX];
queue <int> Q;

int Bellman(int S) {
    for(int i = 1; i <= N; ++i) {
        d[ i ] = oo;
        inQ[ i ] = 0;
        used[ i ] = 0;
    }


    Q.push( S );
    d[ S ] = 0;
    inQ[ S ] = 1;

    while( !Q.empty() ) {
        int node = Q.front();
        Q.pop();
        inQ[ node ] = 0;
        if ( ++used[ node] == N) {
            return 0;
        }
        for (vector< edge >::iterator it = G[node].begin(); it != G[node].end(); ++it) {
            if (d[ node ] + it->c < d[ it-> n]) {
                d[ it->n ] = d[ node ] + it->c;
                if (!inQ[ it->n ]) {
                    inQ[ it->n ] = 1;
                    Q.push( it->n );
                }
            }
        }
    }

    return 1;
}

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

    scanf("%d%d", &N, &M);
    while (M--) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        G[x].push_back( edge(y, c) );
    }

    if ( !Bellman(1) ) {
        printf("Ciclu negativ!\n");
        return 0;
    }

    for (int i = 2; i <= N; ++i) {
        printf("%d ", d[ i ]);
    }
    printf("\n");

    return 0;
}