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

#define NMAX 50000
#define MMAX 250000

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

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

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

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

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

    memset(d, 0x7F, sizeof d);

    cht = chh = 0;
    d[1] = 0;
    ch[cht++] = 1;

    while (chh < cht) {
        for (j = adj_list[ch[chh]]; j != 0; j = edges[j].n) {
            if (edges[j].w + d[edges[j].u] < d[edges[j].v]) {
                d[edges[j].v] = edges[j].w + d[edges[j].u];
                ch[cht++] = edges[j].v;
            }
        }

        chh++;
    }

    for (i = 1; 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;
}