#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;

typedef struct qNod{
	struct qNod *next;
	int info;
}qNod;

Nod *G[NMAX];
qNod *first = NULL, *last = NULL;

int front(){
    return first->info;
}

void pop(){
    qNod *aux = first;
    if(first->next != NULL){
        aux = aux->next;
        free(first);
        first = aux;
    }
    else {
        free(first);
        first = NULL;
        last = NULL;
    }
}

void push(int data){
    if(last == NULL){
        last = (qNod*)malloc(sizeof(qNod));
        last->info = data;
        last->next = NULL;
        first = last;
    }
    else{
        qNod *aux = (qNod*)malloc(sizeof(qNod));
        last->next = aux;
        aux->info = data;
        aux->next = NULL;
        last = aux;
    }
}

int empty(){
    return (first == NULL  && last == NULL);
}

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

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

	push(start);

	viz[start] = 1;
	dmin[start] = 0;
	while (!empty() && ok == 1 ){
		int prec = front();
		pop();

		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){

                    push(p->vf);
                    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 {
        while (first != NULL)
            pop();
		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;
}