#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define file_in "bellmanford.in"
#define file_out "bellmanford.out"

#define mkp make_pair
#define pb push_back
#define f first
#define s second
#define Inf 0x3f3f3f3f
#define Nmax 301000

int c[Nmax];
int n,m;
vector<int> q;
vector< pair< int,int > > G[Nmax];

void citire()
{
	int a,b,c;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	for (int i=1;i<=m;++i)
	{
		scanf("%d %d %d", &a, &b, &c);
		G[a].pb(mkp(b,c));
	}
}


void init()
{
	for (int i=2;i<=n;++i)
		 c[i]=Inf;
}


void bellman()
{
	int nr=0,p,u,i,nod;
	
	int viz[Nmax];
	q.pb(1);
	
	p=u=0;
	
	while(p<=u)
	{
		nod=q[p];
		viz[nod]=0;
		for (i=0;i<G[nod].size();++i)
			 if (c[nod]+G[nod][i].s<c[G[nod][i].f])
			 {
				 c[G[nod][i].f]=G[nod][i].s+c[nod];
				 if (viz[G[nod][i].f]==0)
				 {
					 viz[G[nod][i].f]=1;
					 q.pb(G[nod][i].f);
					 u++;
				 }
				 nr++;
			 }
		p++;
	if (nr>=Nmax)
		break;
	}
}

int ciclu()
{
	for (int i=1;i<=m;++i)
		for (int j=0;j<G[i].size();++j) 
		     if (c[i]+G[i][j].s<c[G[i][j].f])
				 return 1;
	return 0;
}	


int main()
{
	citire();
	init();
	bellman();
	if (ciclu())
		printf("Ciclu negativ!\n");
	else
		for (int i=2;i<=n;++i)
			 printf("%d ", c[i]);
    
	fclose(stdin);
    fclose(stdout);


}