#include<stdio.h>
#include<queue>
#define MAX 50001
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,j,d[MAX],a,b,c,X = 1,ok,viz[MAX],nr[MAX],M[3][6*MAX],cont;
queue<int> Q;
void add(int x,int y,int c)
{
	if(!M[0][x])
	{
		M[1][x] = cont;
	}
	else
	{
		M[1][M[0][x]] = cont;
	}
	M[0][cont] = y;
	M[2][cont] = c;
	M[0][x] = cont;
	++cont;
}
int BellmanFord()
{
	Q.push(1);
	viz[X] = 1;
	nr[X] = 1;
	int var;
	while(!Q.empty())
	{
		a = Q.front();
		var = M[1][a];
		while(var)
		{
			b = M[0][var];
			c = M[2][var];
			if(d[b] > d[a] + c)
			{
				d[b] = d[a] + c;
				if(!viz[b])
				{
					if(nr[b]+1 > n)
						return 0;
					++nr[b];
					viz[b] = 1;
					Q.push(b);
				}
			}
			var = M[1][var];
		}
		viz[Q.front()] = 0;
		Q.pop();
	}
	return 1;
}
int main()
{
	FILE*f = fopen("bellmanford.in","r");
	fscanf(f,"%d%d",&n,&m);
	cont = n+1;
	for(i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&a,&b,&c);
		add(a,b,c);
		if(i<=n)
			d[i] = INF;
		
	}
	fclose(f);
	d[X] = 0;
	FILE*g = fopen("bellmanford.out","w");
	if(!BellmanFord())fprintf(g,"Ciclu negativ!\n");
	else
		for(i=2;i<=n;++i)
			fprintf(g,"%d ",d[i]);
	fclose(g);
	return 0;
}