#include<fstream>
#include<vector>
#define pb push_back
#define NN 50001
#define INF 0x3f3f3f3f
using namespace std;
ofstream out("bellmanford.out");
struct Q{
	int vf,cost;
	Q(int v,int c)
	{
		vf=v;
		cost=c;
	}
};
vector<Q>G[NN];
int d[NN],v[NN],n,m;
void citire();
void BEL(int start);
int main()
{
	citire();
	BEL(1);
	return 0;
}
void citire()
{
	ifstream in("bellmanford.in");
	in>>n>>m;
	int i,j,c;
	for(;m;m--)
	{
		in>>i>>j>>c;
		G[i].pb(Q(j,c));
	}
	for(i=1;i<=n;i++)
		for(j=0;j<G[i].size();j++)
			if(G[i][j].cost==0)
			G[i][j].cost=INF;
}
void BEL(int start)
{
	int i,j,k,ok;
	for(i=1;i<=n;i++)
		d[i]=INF;
	d[start]=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(i=2;i<=n;i++)
				out<<d[i]<<" ";
		}
		
}