#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], 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;
}