#include<stdio.h>
#include<vector>
using namespace std;
#define nmax 50005
#define inf 1<<30
struct element{long n, c;};
long n, m, i, a, b, c, dmin[nmax], pas, inc, x;
vector <long> co;
vector <element> ma[nmax];
vector <element>::iterator it;
bool ok, einc[nmax];
element el;

void citire()
{
	scanf("%ld %ld",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%ld %ld %ld",&a,&b,&c);
		el.n=b;	el.c=c;		ma[a].push_back(el);
	}
}

void rezolvare()
{
	for (i=2;i<=n;i++)
		dmin[i]=inf;
	co.push_back(1);
	while (inc<co.size())
	{
		x=co[inc];	inc++;	einc[x]=0;
		for (it=ma[x].begin();it!=ma[x].end();it++)
			if (dmin[(*it).n]>dmin[x]+(*it).c)
			{
				dmin[(*it).n]=dmin[x]+(*it).c;
				if (!einc[(*it).n])
					co.push_back((*it).n);
				einc[(*it).n]=1;
			}
		if (inc==n*m+1)
			break;
	}
	for (i=1;i<=n;i++)
		for (it=ma[i].begin();it!=ma[i].end();it++)
			if (dmin[i]+(*it).c<dmin[(*it).n])
				ok=0;
	
}

int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	citire();
	ok=1;
	rezolvare();
	if (ok)
		for (i=2;i<=n;i++)
			printf("%ld ",dmin[i]);
	else
		printf("Ciclu negativ!");
	return 0;
}