// http://infoarena.ro/problema/bellmanford

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

#define INF INT_MAX

typedef struct node {
	int b;
	short cost;
	struct node *next;
} Node;

Node **Next;
int n, m;

int *Cost;

int bellmanFord(int here) {
	int *inQ = (int*)calloc(n, sizeof(int));
	int i, numQ;
	for (i = 0; i < n; ++ i)
		Cost[i] = INF;
	Cost[here] = 0;
	inQ[here] = 1;
	numQ = 1;

	Node *begin, *end = (Node*)calloc(1, sizeof(Node)),
	     *curr, *helper;
	end->b = here;
	char negativeCycle = 0;

	for (begin = end; begin != NULL; begin = helper) {
		here = begin->b;
		inQ[here] = 0;
		-- numQ;

		for (curr = Next[here]; curr != NULL; curr = curr->next) {
			if (Cost[here] == INF)
				break;
			if (Cost[curr->b] > Cost[here] + curr->cost) {
				Cost[curr->b] = Cost[here] + curr->cost;

				if (!inQ[curr->b]) {
					helper = (Node*)calloc(1, sizeof(Node));
					helper->b = curr->b;
					helper->next = NULL;
					end->next = helper;
					end = helper;

					inQ[curr->b] = 1;
					++ numQ;

					if (numQ > n) {
						goto end;
						negativeCycle = 1;
					}
				}
			}
		}

		helper = begin->next;
		free(begin);
	}
end:
	for (curr = begin; curr != NULL; curr = helper) {
		helper = curr->next;
		free(curr);
	}
	free(inQ);

	return negativeCycle;
}

void addNext(int a, int b, int cost) {
	Node *helper = (Node*)calloc(1, sizeof(Node));
	helper->b = b;
	helper->cost = cost;
	helper->next = Next[a];

	Next[a] = helper;
}

void eraseNext() {
	int i;
	Node *curr, *helper;
	for (i = 0; i < n; ++ i) 
		for (curr = Next[i]; curr != NULL; curr = helper) {
			helper = curr->next;
			free(curr);
		}	
	free(Next);
}

int main() {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	scanf("%d%d", &n, &m);
	Next = (Node**)calloc(n, sizeof(Node*));

	int i, a, b;
	short c;
	for (i = 0; i < m; ++ i) {
		scanf("%d%d%hd", &a, &b, &c);
		addNext(a - 1, b - 1, c);
	}

	Cost = (int*)calloc(n, sizeof(int));
	char negativeCycle = bellmanFord(0);
	if (!negativeCycle) {
		for (i = 1; i < n; ++ i)
			printf("%d ", Cost[i]);
		printf("\n");
	} else
		printf("Ciclu negativ!\n");

	eraseNext();
	free(Cost);
	return 0;
}