/*
 * @ Copyright, 3.05.2010
 * Mihai Tabără
 * 325 CA
 * Lab 8 [ PA ]
 * Time Complexity - O(N^2)
 * Language used: C
 * Operating System: Ubuntu 9.10
 * Environment: Vim
 */

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

#define NMAX 50005
#define DIM 3000000

const char *in = "bellmanford.in";
const char *out = "bellmanford.out";
const int INF = (1<<30);

typedef struct nod {
	int vf;
	int c;
	struct nod *next;
} *PNOD, NOD;

PNOD L[NMAX];

int N, M;
int dp[NMAX], f[NMAX];
char sel[NMAX];

void Add (int i, int j, int c)
{
	PNOD p = (PNOD) calloc (1, sizeof(NOD));
	p->vf = j;
	p->c = c;
	p->next = L[i];
	L[i] = p;
}

int BF(void)
{
	PNOD prim, ultim, p;
	prim = ultim = NULL;
	int i, j, c;

	for (i = 1; i <= N; ++i)
	{
		dp[i] = INF;
		sel[i] = 0;
		f[i] = 0;
	}

	prim = ultim = (PNOD)calloc (1, sizeof(NOD));
	prim->vf = 1;
	prim->next = NULL;

	dp [sel[f[1] = 1] = 1] = 0;

	while (prim)
	{
		i = prim->vf;
		sel[i] = 0;
		for (p = L[i]; p; p = p->next)
		{
			j = p->vf;
			c = p->c;
			if (dp[j] > dp[i] + c)
			{
				dp[j] = dp[i] + c;
				if (!sel[j])
				{
					sel[j] = 1;
					if (f[j]++ > N)
						return 0;
					PNOD t = (PNOD)calloc (1, sizeof(NOD));
					t->vf = j;
					t->next = NULL;
					ultim->next = t;
					ultim = ultim->next;
				}
			}
		}
		PNOD t = prim;
		prim = prim->next;
		free (t);
	}
	return 1;
}

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

	scanf ("%d%d", &N, &M);
	int i, j, c;

	for (; M; --M)
	{
		scanf ("%d%d%d", &i, &j, &c);
		Add (i, j, c);
	}

	BF();
	if (!BF()) printf ( "Ciclu negativ!\n");
	else
	{
		for (i = 2; i <= N; ++i)
			printf ("%d ", dp[i]);
	}

	return 0;
}