#include<fstream>
#include<vector>
#define NN 50001
#define INF 0x3f3f3f
using namespace std;
ofstream out("bellmanford.out");
int n,d[NN],m;
struct cc{
int vf;
int cost;
	cc(int v,int c)
	{
		vf=c;
		cost=c;
	}
};
vector<cc>G[NN];
void read();
int ford(int s);
int main()
{
	read();
	ford(1);
	return 0;
}
void read()
{
	ifstream in("bellmanford.in");
	in>>n>>m;
	int x,y,c;
	for(;m;m--)
	{
		in>>x>>y>>c;
		G[x].push_back(cc(y,c));
	}
}
int ford(int s)
{
	int i,j,k,ok;
	for(int i=1;i<=n;i++)
		d[i]=INF;
	d[s]=0;
	for(i=1;i<=n;i++)
	{
		ok=0;
		for(j=1;j<=n;j++)
			for(k=0;k<G[j].size();k++)
				if(d[j]!=INF&&G[j][k].cost!=INF)
					if(d[G[j][k].vf]>d[j]+G[j][k].cost)
					{
						d[G[j][k].vf]=d[j]+G[j][k].cost;
						ok=1;
					}
	}
	if(ok)
	out<<"Ciclu negativ!";
	else
	{
		for(int i=2;i<=n;i++)
			out<<d[i]<<" ";
	}
	return 0;
}