#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
std::ifstream cin("bellmanford.in");
std::ofstream cout("bellmanford.out");
using namespace std;
#define maxn 50009
#define inf 0x3f3f3f3f
vector<pair<int,int> > g[maxn];
int n,m;
int in_q[maxn],counter[maxn],sol[maxn];
queue<int> que;

bool bellmanFord(int x){
	memset(sol,inf,sizeof(sol));
	in_q[x]=1;
	sol[x]=0;
	counter[x]++;
	que.push(x);
	while(!que.empty()){
		int nod=que.front();
		que.pop();
		in_q[nod]=0;
		for(auto it=g[nod].begin();it!=g[nod].end();it++){
			if(counter[it->first]>n)
				return 0;
			else
				if(sol[it->first]>sol[nod]+it->second){
					sol[it->first]=sol[nod]+it->second;
					in_q[it->first]=1;
					counter[it->first]++;
					que.push(it->first);
				}
		}
	}
	return 1;
}
/*
//Merge si asa, fara ca alg bellmanFord sa fie optimizat,
long check_negativ()// dar trebuie in while ca
{ 									// pas<N*M!!
	long i;
	for(i=1; i<=m; i++)
			if(cost[e[i].a]+e[i].c<cost[e[i].b])
					return 1;
	return 0;
}
*/
int main()
{
		int x,y,c,nod=1;
		cin>>n>>m;
		for(;m--;){
			cin>>x>>y>>c;
			g[x].push_back(make_pair(y,c));
		}
		if(bellmanFord(1))
			for(int i=1;i<=n;i++){
				if(i!=nod)
					cout<<sol[i]<<' ';
			}
		else
			cout<<"Ciclu negativ!";
		return 0;
}