#include <bits/stdc++.h>

using namespace std;

const int NMAX = 50001;
const int INF = 1000000000;

int N, M;
int d[NMAX], counter[NMAX];
vector<pair<int, int>> G[NMAX];
bitset<NMAX> inQueue;

void read() {
    scanf("%d %d\n", &N, &M);
    while (M--) {
        int x, y, c;
        scanf("%d %d %d\n", &x, &y, &c);
        G[x].emplace_back(y, c);
    }
}

bool bellmanFord() {
    fill(d + 1, d + N + 1, INF);

    d[1] = 0;
    counter[1] = 1;

    queue<int> q;
    q.push(1);

    while (!q.empty()) {
        int x = q.front(), y, c;
        q.pop();

        inQueue[x] = false;

        for (auto next: G[x]) {
            tie(y, c) = next;
            if (d[x] + c < d[y]) {
                d[y] = d[x] + c;

                if (!inQueue[y]) {
                    inQueue[y] = true;
                    q.push(y);

                    ++counter[y];
                    if (counter[y] >= N) return false;
                }
            }
        }
    }

    return true;
}

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

    read();
    if (!bellmanFord()) {
        puts("Ciclu negativ!");
    } else {

        for (int i = 2; i <= N; i++)
            printf("%d ", d[i] == INF ? 0 : d[i]);
    }

    return 0;
}