#include <stdio.h>
 
#define INF 50000002
#define DIM 50010
 
struct nod {
    int inf;
    int cost;
    nod *adr;
};
 
nod *V[DIM], *q, *r;
int N, M, X, Y, C, i, j, k, ok;
int D[DIM];
 
struct coada {
    int inf;
    coada *adr;
};
int nrInStack[DIM], inStack[DIM];
coada *c, *p, *u;
 
int main() {
    FILE *f = fopen("bellmanford.in","r");
    FILE *g = fopen("bellmanford.out","w");
    fscanf(f,"%d %d",&N, &M);
    for (i=2;i<=N;i++) {
        D[i] = INF;
    }
    for (i=1;i<=M;i++) {
        fscanf(f,"%d %d %d",&X, &Y, &C);
        q = new nod;
        q->inf = Y;
        q->cost = C;
        q->adr = V[X];
        V[X] = q;
    }
    fclose(f);
     
     
    c = new coada;
    c->inf = 1;
    c->adr = NULL;
    u = c;
    inStack[1] = 1;
    nrInStack[1] = 1;
    ok = 1;
    while (c && ok) {
        p = c;
         
        inStack[p->inf] = 0;
        for (r = V[p->inf];r!=NULL;r = r->adr) {
            if (D[r->inf] > D[p->inf] + r->cost) {
                D[r->inf] = D[p->inf] + r->cost;



                if (inStack[r->inf] == 0) {

	            inStack[r->inf] = 1;
        	    nrInStack[r->inf]++;
               	    if (nrInStack[r->inf] > N)
	            	ok = 0;

                    u->adr = new coada;
                    u = u->adr;
                    u->adr = NULL;
                    u->inf = r->inf;
                }
            }
        }
        c = c->adr;
        delete p;
    }
     
     
    if (ok == 0) {
        fprintf(g,"Ciclu negativ!\n");
    } else {
        for (i=2;i<=N;i++)
            fprintf(g,"%d ",D[i]);
    }
     
    return 0;
}