#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define NMAX 50005
#define MMAX 250005
#define INF 2e7
#define PLL pair < long , long >
int n , m,x,y,z;
int exst[NMAX],d[NMAX];

vector< int > v[NMAX] ;
vector< PLL >  h ;
struct muchie
{
	int a,b,c;
}  e[MMAX];
void bellford()
{
	
	PLL prche;
	for(int i=2;i<=n;++i)
	{
		
		d[i]=INF;
	}
	long pas=0 ;
	while(h.size() && pas<=1LL*n*m)		
	{
		pop_heap(h.begin(),h.end () ) ;

		prche = h.back();

		h.pop_back();

		int x1 =prche.second;

		exst[x1]=0;
		++pas;
		for(int j=0 ; j < v[x1].size() ; ++j)
		{
			int y1=v[x1][j];

			x=e[y1].a;
			y=e[y1].b;
			z=e[y1].c;

			if( d[ y ] > d[ x ] + z )			
			{
				d[ y ] = d[ x ]+z;
				if(!exst[y])
				{
					exst[y]=1;
					h.push_back (make_pair (-d[y],y));
					push_heap(h.begin(),h.end());
				}
			}
		}
	}

}
int check()
{
	for(int j=1;j<=m;++j)
	{
		x=e[j].a;
		y=e[j].b;
		z=e[j].c;
		if(d[y]>d[x]+z) return 1;
	}
	return 0;
}

void citeste()
{
	scanf("%d %d",&n,&m);
	for ( int i=1 ;i<=m; ++i)	
	{
		scanf("%d %d %d", &e[i].a,&e[i].b,&e[i].c);
		v[e[i].a].push_back(i);
	}
	d[1] = 0 ;
	h.push_back (make_pair(0,1));
	make_heap( h.begin() , h.end() ) ;

}

int main()
{
	freopen("bellmanford.in", "r",stdin);
	freopen("bellmanford.out","w",stdout);
	citeste();
	bellford();
	if(check() )printf( "Ciclu negativ!\n" );
	else	
	 for(int i=2;i<=n;++i)printf("%d ",d[i]);
	
	return 0 ;
}