#include <bits/stdc++.h>

using namespace std;

const int MMAX = 250001;
const int NMAX = 50001;
int dist[NMAX];

const int INF = 1e9;

struct ura {int a, b, cost;};

ura muchii[MMAX];

int main() {

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

    int n, m, i, j, pp;

    scanf ("%d%d", &n, &m);

    for (i = 1; i <= m; i++) {
        scanf ("%d%d%d", &muchii[i].a, &muchii[i].b, &muchii[i].cost);
    }

    for (i = 2; i <= n; i++) {
        dist[i] = INF;
    }
    dist[1] = 0;

    for (i = 1; i < n; i++) {
        for (j = 1; j <= m; j++) {
            if (dist[muchii[j].a] + muchii[j].cost < dist[muchii[j].b])
                dist[muchii[j].b] = dist[muchii[j].a] + muchii[j].cost;
        }
    }

    pp = 0;
    for (j = 1; j <= m && pp == 0; j++) {
        if (dist[muchii[j].a] + muchii[j].cost < dist[muchii[j].b])
            pp = -1;
    }

    if (pp == -1)
        printf ("Ciclu negativ!");
    else
        for (i = 2; i <= n; i++)
            printf ("%d ", dist[i]);

    return 0;
}