#include <fstream>
#define MAXN 999999999
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct Nod{int inf,c; Nod* leg;};
typedef Nod* nod;

nod a[50001];
int cost[50001],numar[50001],n,m,w,t,inc,sf;
unsigned short q[800001];

void add(int x, int y,int co)
{
	nod p=new Nod;
	p->inf=y;
	p->c=co;
	p->leg=a[x];
	a[x]=p;
}

int main()
{
	int x,y,c,i;
	fin>>n>>m;
	for(i=1; i<=m; i++)
	{
		fin>>x>>y>>c;
		add(x,y,c);
		cost[i]=MAXN;
	}
	cost[1]=0;
	//viz[1]=1;
	numar[1]=1;
	inc=1;sf=1;
	q[1]=1;
	while (inc<=sf)
	{
		for(nod p=a[q[inc]];p;p=p->leg)
			if(cost[p->inf]>cost[q[inc]]+p->c)
			{
				cost[p->inf]=cost[q[inc]]+p->c;
				//if(!viz[p->inf])
				//{
					sf++;
					q[sf]=p->inf;
					//viz[p->inf]=1;
					numar[p->inf]++;
				//}
				if(numar[p->inf]>n){fout<<"Ciclu negativ!"; return 0;}
			}
		//viz[q[inc]]=0;
		inc++;
	}
	for(i=2; i<=n; i++) fout<<cost[i]<<" ";
	return 0;
}