#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f
using namespace std;
int n,m,i,j,k,x,y;
short int d[50001];
vector<pair<int,int>>G[50001];
queue<int>Q;
int c[50001];
bool inq[50001],flag;
bool bf()
{
	Q.push(1);inq[1]=1;
	while(!Q.empty()&&!flag)
	{
		int Nod=Q.front();Q.pop();
		inq[Nod]=0;
		for(i=0;i<G[Nod].size();i++)
		{
			int Vecin=G[Nod][i].first,Cost=G[Nod][i].second;
			if(d[Nod]+Cost<d[Vecin])
			{
				if(c[Vecin]==n)
				{
					flag=1;
					break;
				}
				d[Vecin]=d[Nod]+Cost;
				if(!inq[Vecin])
				{
					inq[Vecin]=1;
					Q.push(Vecin);
				}
				c[Vecin]++;
			}
		}
	}
	return flag;
}
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int main()
{
	fin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		fin>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
	}
	for(i=2;i<=n;i++)
		d[i]=INF;
	if(bf())
		fout<<"Ciclu negativ!\n";
	else
		for(i=2;i<=n;i++)
			fout<<d[i]<<" ";
	fout<<"\n";
	return 0;
}