#include <stdio.h>
#include <vector>
#define nmax 50005
#define inf nmax*1000
using namespace std;
struct element{long n, c;};

long i, n, m, a, rez[nmax], viz[nmax], x, inc;
vector <long> co;
vector <element> v[nmax];
vector <element> :: iterator it;
element el;
bool ok;

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

void rezolvare()
{
	ok=1;	co.push_back(1);	
	while((inc<co.size())&&(ok))
	{
		x=co[inc];	inc++;
		for (it=v[x].begin();it!=v[x].end();it++)
			if (rez[(*it).n]>rez[x]+(*it).c)
			{
				rez[(*it).n]=rez[x]+(*it).c;
				co.push_back((*it).n);
				viz[(*it).n]++;
				if (viz[(*it).n]==n)
				{	printf("Ciclu negativ!");	ok=0; break;}
			}
	}
}

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