#include <stdio.h>
#include <stdlib.h>

int *E[50000];
int *C[50000];
int En[50000];

int Q[50001];
int qn;

char Inq[50000];
int Qt[50000];

int Dist[50000];

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

    int v, e;
    scanf("%i%i", &v, &e);

    int i;
    for (i = 0; i < e; ++i) {
        int x, y, c;
        scanf("%i%i%i", &x, &y, &c);

        --x;
        --y;

        E[x] = realloc(E[x], (En[x] + 1) * sizeof(int));
        C[x] = realloc(C[x], (En[x] + 1) * sizeof(int));

        E[x][En[x]] = y;
        C[x][En[x]] = c;

        En[x]++;
    }

    Q[qn++] = 0;
    Inq[0] = 1;
    Qt[0] = 1;

    i = 0;
    while (1) {
        if (i == qn) break;

        int b = Q[i];

        ++i;
        if (i > v) i = 0;

        Inq[b] = 0;

        int j;
        for (j = 0; j < En[b]; ++j) {
            int e = E[b][j];
            int c = C[b][j];

            if (!Qt[e] || Dist[e] > Dist[b] + c) {
                Dist[e] = Dist[b] + c;

                if (!Inq[e]) {
                    Q[qn++] = e;
                    if (qn > v) qn = 0;

                    Inq[e] = 1;
                    ++Qt[e];

                    if (Qt[e] == v) {
                        printf("Ciclu negativ!\n");
                        goto done;
                    }
                }
            }
        }
    }

    for (i = 1; i < v; ++i) {
        if (i > 1) printf(" ");
        printf("%i", Dist[i]);
    }
    printf("\n");

    done:
    return 0;
}