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

struct list{
    int v;
    int cost;
    struct list *next;
} *E[50001];
int N, M, D[50001];
int queue[2][50001];
int used[50001];

int main()
{
    FILE *in = fopen("bellmanford.in", "r");
    FILE *out = fopen("bellmanford.out", "w");
    int i, j, ok, a, b, c, choose;
    struct list *p;

    fscanf(in, "%d %d", &N, &M);
    for(i = 0; i < M; ++i)
    {	
		fscanf(in, "%d %d %d", &a, &b, &c);
		p = malloc(sizeof(struct list));
		p->v = b;
		p->cost = c;
		p->next = E[a];
		E[a] = p;
    }

    for(i = 1; i <= N; ++i)
		D[i] = 1 << 29;
    
	D[1] = 0;
	choose = 0;
	queue[choose][1] = 1;
    queue[choose][0] = 1;
    used[1] =1;

    for(ok = 1, i = 1; i <= N && ok; ++i)
    {
		for(ok = 0, j = 1; j <= queue[choose][0]; ++j)
			for(a = queue[choose][j], p = E[ queue[choose][j] ]; p; p = p->next)
				if(D[a] + p->cost < D[p->v])
				{
					ok = 1;
					D[p->v] = D[a] + p->cost;
					if(used[p->v] != i)
					{
						used[p->v] = i;
						queue[1-choose][0]++;
						queue[1-choose][ queue[1-choose][0] ] = p->v;
					}
				}
				
		queue[choose][0] = 0;
		choose = 1 - choose;
    }
	
	if(ok)
		fprintf(out, "Ciclu negativ!\n");
    else
    {
		for(i = 2; i <= N; ++i)
			fprintf(out, "%d ", D[i]);
		fprintf(out, "\n");
    }

    fclose(in);
    fclose(out);
    return 0;
}