#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1000000010
#define MAXN 51000
#define MAXM 250100

using namespace std;

vector < pair<int,int> > G[MAXN];
queue<int > Q;
bool ok[MAXN];
bool negativ;
int dist[MAXN], nr[MAXN];
int i,j,n,m,x,cost,y;


int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1; i<=m; i++){
		scanf("%d %d %d",&x,&y,&cost);
		G[x].push_back(make_pair(y,cost));
	}
	for (i=1; i<=n; i++){
		dist[i]=INF;
		ok[i]=false;
	}
	Q.push(1);
	dist[1]=0; negativ = false; ok[1]=true;
	while (!Q.empty() && !negativ){
		x = Q.front();
		Q.pop();
		ok[x]=false;
		vector<pair<int, int> > ::iterator it;
		if (dist[x]>=INF) continue;
		for (it=G[x].begin(); it!=G[x].end(); it++)
			if (dist[it->first] > dist[x] + it->second){
				dist[it->first] = dist[x] + it->second;
				if (!ok[it->first]){
					if (nr[it->first] > n)
						negativ = true;
					else {
						Q.push(it->first);
						ok[it->first]=true;
						nr[it->first]++;
					}
				}
			}
	}
	if (negativ)
		printf("Ciclu negativ!\n");
	else {
		for (i=2; i<=n; i++)
			printf("%d ",dist[i]);
		printf("\n");
	}
	return 0;
}