// Catalin Balan
// Thu Feb 25 19:06:33 EET 2010
// Infoarena - Algoritmul lui Belman-Ford

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <bitset>
#define INF 0x3f3f3f3f

using namespace std;

#define	NMAX 50004
#define CHUNK 8192

#define FIN "belmanford.in"
#define FOUT "belmanford.out"

char g_buf[CHUNK];
int g_p=CHUNK-1;

inline int get(FILE *f)
{

	int x = 0, alfa = 1;
	while ((g_buf[g_p] < '0' || g_buf[g_p] > '9') && g_buf[g_p] != '-')
		if (++g_p == CHUNK) fread(g_buf,1,CHUNK,f), g_p=0;

	if (g_buf[g_p] == '-') 
	{
		alfa = -1;
		if (++g_p == CHUNK) fread(g_buf,1,CHUNK,f), g_p=0;
	}
	
	while (g_buf[g_p] >= '0' && g_buf[g_p] <= '9')
	{
		x = x*10 + g_buf[g_p]-'0';
		if (++g_p == CHUNK) fread(g_buf,1,CHUNK,f), g_p=0;
	}
	return x * alfa;
}

struct muchie
{
	int next, cost;
};

int n,m;
vector<muchie> G[NMAX];
int dist[NMAX];
int count[NMAX];

int main(int argv, char ** argc)
{
	FILE *f = fopen(FIN, "r");
	FILE *g = fopen(FOUT, "w");

	n = get(f);
	m = get(f);
	muchie aux;
	int x;

	for (int i = 1; i <= m; ++i)
	{
		x 			= get(f);
		aux.next	= get(f);
		aux.cost 	= get(f);
		G[x].push_back(aux);
	}

	queue<int> Q;
	bitset<NMAX> inQ(false);
	for (int i = 2; i <= n; ++i)
		dist[i] = INF;

	inQ[1] = true;
	Q.push(1);
	dist[1] = 0;

	int now;
	while (!Q.empty())
	{
		now = Q.front();
		Q.pop();
		inQ[now] = false;

		for (vector<muchie>::iterator it = G[now].begin(); it != G[now].end(); ++it)
		{
			if ( dist[now] + it->cost >= dist[ it->next ]) continue;
			dist[ it->next ] = dist[now] + it->cost;
			
			if (inQ[ it->next ]) continue;
			Q.push( it->next );
			inQ[ it->next ] = true;

			if( (++count[ it->next ] ) > n )
			{
				fprintf(g,"Ciclu negativ!\n");
				fclose(f);
				fclose(g);
				return EXIT_SUCCESS;
			}
			
		}

	}

	for (int i = 2; i <= n; ++i)
		fprintf(g,"%d ", dist[i]);


	fclose(f);
	fclose(g);
	return EXIT_SUCCESS;
}