#include<fstream>
#include<vector>
#include<queue>
#define M 50005
#define INF 1000000000
#define mp make_pair
#define pb push_back
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

typedef vector<pair<long,long> > VI;
VI a[M];
VI::iterator it;
queue<long> q;
long n,m,viz[M],d[M],nr[M];

void cit()
{
	long i,x,y,z;
	f>>n>>m;
	
	for(i=1;i<=m;++i)
	{
		f>>x>>y>>z;
		a[x].pb(mp(y,z));
	}
	
	f.close();
}

int bell()
{
	long i,k;
	for(i=2;i<=n;++i)
		d[i]=INF;
	
	d[1]=viz[1]=0;
	q.push(1);
	
	while(!q.empty())
	{
		k=q.front();
		q.pop();
		viz[k]=0;
		
		for(it=a[k].begin();it!=a[k].end();++it)
		{
			if(d[(*it).first]>d[k]+(*it).second) {d[(*it).first]=d[k]+(*it).second;
												  nr[(*it).first]++;
												  if(nr[(*it).first]==n) return 0;
												  if(viz[(*it).first]==0) {viz[(*it).first]=1;
																		    q.push((*it).first);}
												 }
		}
	}
	
	return 1;
}
	
int main()
{
	cit();
	
	if(bell()==0) g<<"Ciclu negativ!\n";
	else {long i;
		  for(i=2;i<=n;++i)
			  g<<d[i]<<" ";
		  g<<"\n";}
	
	g.close();
	return 0;
}