#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
#define maxn 50010
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,d[maxn],cn[maxn];
const int inf = 0x3f3f3f3f; 
bool cnv=false;
vector< pair<int,int> > e[maxn];

void citire(){
	int x,y,c;
	f>>n>>m;
	for(int i=1;i<=m;i++){
		f>>x>>y>>c;
		e[x].push_back(make_pair(y,c));
	}
}

void bellman(){
	bool test[maxn];
	queue<int> Q;
	memset(d,inf,sizeof(d));
	memset(test,false,sizeof(test));
	d[1]=0;
	test[1]=true;
	Q.push(1);
	while(!Q.empty()&&!cnv){
		int nod=Q.front();
		Q.pop();
		test[nod]=false;
		for(vector< pair<int,int> >::iterator it=e[nod].begin();it!=e[nod].end();++it)
			if(d[nod]+it->second<d[it->first]){
				d[it->first]=d[nod]+it->second;
				if(!test[it->first])
					if (cn[it->first] > n)                        
						cnv= true;                   
					else {                         
						Q.push(it->first);                         
						test[it->first] = true;                         
						cn[it->first] ++;                   
					} 
			}
	}
}

int main(){
	citire();
	bellman();
	if(!cnv)
		for(int i=2;i<=n;i++)
			g<<d[i]<<' ';
	else 
		g<<"Ciclu negativ!";
	g<<'\n';
	g.close();
	return 0;
}