// Bellman _Ford.cpp : Defines the entry point for the console application.
//

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

#define maxn 100005

typedef struct my_list {
	int data, cost;
	struct my_list * next;
} list;

int Vis[maxn], Dist[maxn], Cnt[maxn];

void add_edge(list **head, int val, int cost) {
	if ((*head) == NULL) {
		(*head) = (list*)malloc(sizeof(list));
		(*head)->data = val;
		(*head)->cost = cost;
		(*head)->next = NULL;
	} else {
		list * new_node = (list*)malloc(sizeof(list));
		new_node->data = val;
		new_node->cost = cost;
		new_node->next = (*head);
		(*head) = new_node;
	}
}

void pop(list **first) {
	(*first) = (*first)->next;
}

void push(list **first, list **last, int val) {
	if ((*first) == NULL) {
		(*first) = (list*)malloc(sizeof(list));
		(*first)->data = val;
		(*first)->cost = 0;
		(*first)->next = NULL;
		(*last) = (*first);
	} else {
		list *new_node = (list*)malloc(sizeof(list));
		new_node->cost = 0;
		new_node->data = val;
		new_node->next = NULL;
		(*last)->next = new_node;
		(*last) = new_node;
	}
}

int Bellman(list *G[maxn], int source, int n) {
	list *first = NULL, *last = NULL, *it;
	Dist[source] = 0;
	Vis[source] = 1;
	push(&first, &last, source);
	while (first != NULL) {
		int node = first->data;
		Vis[node] = 0;
		pop(&first);
		for (it = G[node]; it != NULL; it = it->next) {
			if (Dist[it->data] > Dist[node] + it->cost) {
				Dist[it->data] = Dist[node] + it->cost;
				if (Vis[it->data] == 0) {
					Vis[it->data] = 1;
					push(&first, &last, it->data);
					Cnt[it->data]++;
					if (Cnt[it->data] >= n) return 1;
				}
			}
		}
	}
	return 0;
}

int main() {
	FILE *fin = fopen("bellman.in", "r");
	FILE *fout = fopen("bellman.out", "w");
	list *G[maxn];
	int n, m, x, y, c, i, Dist[maxn];
	fscanf(fin, "%d %d", &n, &m);
	for (i = 0; i <= n; i++) {
		G[i] = NULL;
		Dist[i] = (1 << 31) - 1;
	}
	for (i = 0; i < m; i++) {
		fscanf(fin, "%d %d %d", &x, &y, &c);
		add_edge(&G[x], y, c);
	}
	list *first = NULL, *last = NULL, *it;
	Dist[1] = 0;
	Vis[1] = 1;
	push(&first, &last, 1);
	int neg_cicle = 0;
	while (first != NULL && !neg_cicle) {
		int node = first->data;
		Vis[node] = 0;
		pop(&first);
		for (it = G[node]; it != NULL; it = it->next) {
			if (Dist[it->data] > Dist[node] + it->cost) {
				Dist[it->data] = Dist[node] + it->cost;
				if (Vis[it->data] == 0) {
					Vis[it->data] = 1;
					push(&first, &last, it->data);
					Cnt[it->data]++;
					if (Cnt[it->data] >= n) neg_cicle = 1;
				}
			}
		}
	}
	if (neg_cicle) {
		fprintf(fout, "Ciclu negativ!\n");
	} else {
		for (i = 2; i <= n; i++) {
			fprintf(fout, "%d ", Dist[i]);
		}
		fprintf(fout, "\n");
	}
	fclose(fin);
	fclose(fout);
    return 0;
}