#include <stdio.h>
#include <string.h>

#define NMAX 50000
#define MMAX 250000

static int d[NMAX+1];
static struct edge {
    int u, v, w;
} edges[MMAX];

int main(void)
{
    int n, i, m, j;

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

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

    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }

    memset(d, 0x7F, sizeof d);

    d[1] = 0;

    for (i = 1; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (edges[j].w + d[edges[j].u] < d[edges[j].v]) {
                d[edges[j].v] = edges[j].w + d[edges[j].u];
            }
        }
    }

    for (i = 0; i < m; i++) {
        if (edges[i].w + d[edges[i].u] < d[edges[i].v]) {
            puts("Ciclu negativ!");
            return 0;
        }
    }

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

    return 0;
}