#include <iostream>

const int MAXN = 50005, MAXM = 250005;
const long long INF = 0x3f3f3f;

int n, m;

struct edge {
    int src, dest, weight;
} e[MAXM];

long long d[MAXN];

bool negative_cycles;

void ReadData() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d %d %d", &e[i].src, &e[i].dest, &e[i].weight);
}

void Solve() {
    for (int i = 2; i <= n; i++)
        d[i] = INF;

    for (int i = 1; i <= n - 1; i++)
        for (int j = 1; j <= m; j++)
            if (d[e[j].src] + e[j].weight < d[e[j].dest])
                d[e[j].dest] = d[e[j].src] + e[j].weight;

    negative_cycles = false;
    for (int i = 1; i <= m && !negative_cycles; i++) {
        if (d[e[i].src] + e[i].weight < d[e[i].dest])
            negative_cycles = true;
    }
}

void WriteData() {
    if (negative_cycles)
        printf("Ciclu negativ!");
    else
        for (int i = 2; i <= n; i++)
            printf("%lld ", d[i]);
}

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

    ReadData();
    Solve();
    WriteData();

    return 0;
}