#include<fstream>
#include<vector>
#include<queue>

#define MAX 100000000

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector < pair<int,int> > v[50001];
queue < int > q;
vector < pair<int,int> >:: iterator it;
int n,m,d[50001],s[50001];

int main()
{	int i,ok=1,nod,x,y,c;
	fin>>n>>m;
	for(i=2;i<=n;i++)
		d[i]=MAX;
	for(i=1;i<=m;i++)
	{	fin>>x>>y>>c;
		v[x].push_back(make_pair(y,c));
	}
	q.push(1);
	while(!q.empty()&&ok)
	{	nod=q.front();
		for(it=v[nod].begin();it!=v[nod].end();it++)
			if(d[it->first]>d[nod]+it->second)
			{	d[it->first]=d[nod]+it->second;
				q.push(it->first);
				s[it->first]++;
				if(s[it->first]>=n) ok=0;
			}
		q.pop();
	}
	if(ok==0) fout<<"Ciclu negativ!";
	else 
	for(i=2;i<=n;i++)
		fout<<d[i]<<" ";
		
	fin.close();
	fout.close();
	return 0;
}