#include <bits/stdc++.h>

using namespace std;
long long n,m,x,y,z, viz[50003],dp[50003],nod;bool ok;
vector < pair <long long, long long> > graf[50003];
queue <long long> q;
void bellmanford () {
	while(!q.empty()) {
		nod=q.front();q.pop();
		++viz[nod];
		if(viz[nod]>=n) {
			ok=true;
			return;
		}
		for(int i=0;i<(int)graf[nod].size();++i)
			if(dp[graf[nod][i].first]>dp[nod]+graf[nod][i].second) {
				dp[graf[nod][i].first]=dp[nod]+graf[nod][i].second;
				q.push(graf[nod][i].first);
			}
	}
}
int main () {
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%lld%lld", &n, &m);
	for(int i=1;i<=m;++i) {
		scanf("%lld%lld%lld", &x, &y, &z);
		graf[x].push_back(make_pair(y,z));
	}
	for(int i=2;i<=n;++i)
		dp[i]=1e9*1e9;
	q.push(1);
	bellmanford();
	if(ok==true)
		printf("Ciclu negativ!");
	else
		for(int i=2;i<=n;++i)
			printf("%lld ", dp[i]);
	return 0;
}