#include<fstream>
#include<vector>
#define dmax 50003
#define mult 10000000
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;
long long dm[dmax];
struct muchie
{	int v;
	short int cst;
};
vector<struct muchie>g[dmax];
vector<struct muchie>::iterator it;

void bellmanford()
{	int i,k;
	for(i=1;i<=n;i++)
		dm[i]=mult;
	dm[1]=0;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(it=g[i].begin();it<g[i].end();it++)
				if(dm[it->v]>dm[i]+it->cst)
					dm[it->v]=dm[i]+it->cst;
	for(i=1;i<=n;i++)
		for(it=g[i].begin();it<g[i].end();it++)
			if(dm[it->v]>dm[i]+it->cst )
			{	out<<"Ciclu negativ!";	
				return;
			}
	for(i=2;i<=n;i++)
		out<<dm[i]<<" ";	
}	


int main()
{	int i,a,b,c;
	muchie w;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{	in>>a>>b>>c;
		w.cst=c;
		w.v=b;
		g[a].push_back(w);
	}
	in.close();
	bellmanford();
	out.close();
	return 0;
}