#include <cstdio>
#include <vector>
#include <queue>

#define x first
#define c second

using namespace std;

const int kMaxN = 50005;
const int oo = 1000000005;

vector< pair<int, int> > G[kMaxN];
int N, D[kMaxN], Queued[kMaxN];
queue<int> Q;
bool InQ[kMaxN], Cycle;

void Init(int S) {
    for (int X = 1; X <= N; ++X)
        D[X] = oo;
    D[S] = 0;
    Q.push(S), InQ[S] = true;
}

void BellmanFord(int S) {
    for (Init(S); !Q.empty(); Q.pop()) {
        int X = Q.front();
        InQ[X] = false;

        ++Queued[X];
        if (Queued[X] >= N) {
            Cycle = true;
            return;
        }

        for (vector< pair<int, int> >::iterator Y = G[X].begin(); Y != G[X].end(); ++Y) {
            if (D[X]+Y->c < D[Y->x]) {
                D[Y->x] = D[X]+Y->c;
                if (!InQ[Y->x])
                    Q.push(Y->x), InQ[Y->x] = true;
            }
        }
    }
}

void Read() {
    freopen("bellmanford.in", "r", stdin);
    int M; scanf("%d %d", &N, &M);
    for (; M; --M) {
        int X, Y, C;
        scanf("%d %d %d", &X, &Y, &C);
        G[X].push_back(make_pair(Y, C));
    }
}

void Print() {
    freopen("bellmanford.out", "w", stdout);
    if (Cycle) {
        printf("Ciclu negativ!\n");
        return;
    }
    for (int X = 2; X <= N; ++X)
        printf("%d ", D[X]);
    printf("\n");
}

int main() {
    Read();
    BellmanFord(1);
    Print();
    return 0;
}