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

#define NMAX 50000
#define MMAX 250000

static int adj_list[NMAX+1], d[NMAX+1], ch[NMAX+1], cnt_in_ch[NMAX+1];
static unsigned char in_ch[NMAX+1];

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

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

    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;
    in_ch[1] = 1;
    cnt_in_ch[1] = 1;

    while (!cycle && chh != cht) {
        in_ch[ch[chh]] = 0;

        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];

                if (!in_ch[edges[j].v]) {
                    in_ch[edges[j].v] = 1;
                    ch[cht++] = edges[j].v;
                    cht = cht == NMAX + 1 ? 0 : cht;

                    if (cnt_in_ch[edges[j].v] + 1 > n) {
                        cycle = 1;
                        break;
                    }

                    cnt_in_ch[edges[j].v]++;
                }
            }
        }

        chh++;
        chh = chh == NMAX + 1 ? 0 : chh;
    }

    if (cycle) {
        puts("Ciclu negativ!");
        return 0;
    }

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

    return 0;
}