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

#define INF 0x3f3f3f3f
#define NEW(x) (x*)malloc(sizeof(x))

struct NODE
{
	unsigned int info;
	long cost;
	struct NODE *next;
} **list;

struct QUEUE
{
	unsigned int node;
	struct QUEUE *next;
} *qStart = NULL, *qEnd = NULL;

unsigned int N, M, *queueCount;
long *dists;
short *inQueue;

void add(struct NODE **root, unsigned int x, long c)
{
	struct NODE *temp;
	if(*root == NULL)
	{
		*root = NEW(struct NODE);
		(*root) -> next = NULL;
		(*root) -> info = x;
		(*root) -> cost = c;
	}
	else
	{
		temp = NEW(struct NODE);
		temp -> info = x;
		temp -> cost = c;
		temp -> next = *root;
		*root = temp;
	}
}

void push(unsigned int n)
{
	struct QUEUE *temp;
	if(!qStart)
	{
		qEnd = qStart = NEW(struct QUEUE);
		qStart -> node = n;
		qStart -> next = NULL;
	}
	else
	{
		temp = NEW(struct QUEUE);
		temp -> node = n;
		temp -> next = NULL;
		qEnd -> next = temp;
		qEnd = temp;
	}
}

void pop()
{
	struct QUEUE *temp = qStart;
	qStart = qStart -> next;
	free(temp);
}

unsigned int peek()
{
	return qStart -> node;
}

short empty()
{
	return qStart == NULL;
}

void bellmanFord()
{
	unsigned int i, x;
	short cycle = 0;
	struct NODE *iter;

	dists[1] = 0;
	push(1);
	inQueue[1] = 1;

	while(!empty() && !cycle)
	{
		x = peek();
		pop();
		inQueue[x] = 0;
		for(iter = list[x]; iter; iter = iter -> next)
			if(dists[x] < INF)
				if(dists[iter -> info] > dists[x] + iter -> cost)
				{
					dists[iter -> info] = dists[x] + iter -> cost;
				
					if(!inQueue[iter -> info])
					{
						if(queueCount[iter -> info] > N)
							cycle = 1;
						else
						{
							push(iter -> info);
							inQueue[iter -> info] = 1;
							++queueCount[iter -> info];
						}
					}
				}
	}
	
	if(cycle)
		puts("Ciclu negativ!");
	else
	{
		for(i = 2; i <= N; ++i)
			printf("%ld ", dists[i]);
	}
}

int main()
{
	unsigned int i = 0;
	unsigned int x, y;
	long c;

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

	scanf("%u %u", &N, &M);

	dists = (long*)malloc(sizeof(long) * (N + 1));
	list = (struct NODE**)malloc(sizeof(struct NODE*) * (N + 1));
	inQueue = (short*)malloc(sizeof(short) * (N + 1));
	queueCount = (unsigned int*)malloc(sizeof(unsigned int) * (N + 1));

	for(i = 1; i <= N; ++i)
	{
		dists[i] = INF;
		inQueue[i] = queueCount[i] = 0;
		list[i] = NULL;
	}

	for(i = 0; i < M; ++i)
	{
		scanf("%u %u %ld", &x, &y, &c);
		add(&list[x], y, c);
	}
	
	bellmanFord();

	return 0;
}