// 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 50010

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


struct muchie
{
	int urm, cost;
};

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

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

	fscanf(f, "%d %d ", &n, &m);
	muchie aux;
	int x,y,z;

	for (int i = 1; i <= m; ++i)
	{
		fscanf(f, "%d %d %d ", &x, &y, &z);
		aux.urm		= y;
		aux.cost 	= z;
		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->urm ]) continue;
			dist[ it->urm ] = dist[now] + it->cost;
			
			if (inQ[ it->urm ]) continue;

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

			Q.push( it->urm );
			inQ[ it->urm ] = true;
			
		}

	}

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


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