#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 50001
#define inf 0x3f3f3f3f
typedef struct Nod{
    int vf, cost;
    struct Nod *next;
}Nod;
Nod *G[NMAX];

void doBellmanFord(Nod *G[NMAX], int n, int start){
    int Q[NMAX * 10], cnt[NMAX], dmin[NMAX], st, sf;
    int viz[NMAX], ok = 1;

    memset(cnt, 0, sizeof(cnt));
    memset(dmin, inf, sizeof(dmin));
    memset(viz, 0, sizeof(viz));

    st = 0; sf = 0;
    Q[sf] = start;
    sf++;
    viz[start] = 1;
    dmin[start] = 0;
    while (sf > st && ok == 1 ){
        int prec = Q[st];
        st++;
        Nod *p;
        viz[prec] = 0;
        for (p = G[prec]; p != NULL && ok == 1; p = p->next){
            if (dmin[prec] + p->cost < dmin[p->vf]){
                dmin[p->vf] = dmin[prec] + p->cost;
                if (viz[p->vf] == 0){
                    Q[sf] = p->vf;
                    sf++;
                    viz[p->vf] = 1;
                    cnt[p->vf]++;
                }
            }
            if (cnt[p->vf] > n - 1) {
                ok = 0;
            }
        }
    }
    FILE *foutp = freopen("bellmanford.out", "w", stdout);
    if (ok == 1) {
        int i;
        for(i = 2; i <= n; i++)
            printf("%d ", dmin[i]);
    }
    else
        printf("Ciclu negativ!");
    fclose(foutp);
}

int main(){
    FILE* finp = freopen("bellmanford.in", "r", stdin);
    int n, m;
    scanf("%d %d", &n, &m);
    for(; m; m--){
        int i, j, c;
        scanf("%d %d %d", &i, &j, &c);
        Nod *p = (Nod*)malloc(sizeof(Nod));
        p->next = G[i];
        p->vf = j;
        p->cost = c;
        G[i] = p;
    }
    fclose(finp);
    doBellmanFord(G, n, 1);
    int i;
    for(i = 1; i <= n; i++){
        Nod *t;
        for(t = G[i]; t != NULL; t = t->next)
            free(t);
    }
    return 0;
}