#include <bits/stdc++.h>
#define INF 1000000010
#define MAXN 51000
#define MAXM 250100
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector < pair<int,int> > G[MAXN];
queue<int > Q;
bool Sel[MAXN];
bool negativ;
int D[MAXN], Nr[MAXN];
int i,j,N,M,x,c,y;


int main()
{

	f>>N>>M;
	for (int i=1; i<=M; i++){
            f>>x>>y>>c;
            G[x].push_back({c,y});
	}
	for (int i=1; i<=N; i++)
		D[i]=INF, Sel[i]=false, Nr[i]=0;

	Q.push(1);
	D[1]=0; negativ = false; Sel[1]=true;
	while (!Q.empty() && !negativ){
		x = Q.front();
		Q.pop();
		Sel[x]=false;
		if (D[x]>=INF) continue;
		for (auto i : G[x])
			if (D[i.second] > D[x] + i.first){
				D[i.second] = D[x] + i.first;
				if (!Sel[i.second]){
					if (Nr[i.second] > N) negativ = true;
					else {
						Q.push(i.second);
						Sel[i.second]=true;
						Nr[i.second]++;
					}
				}
			}
	}
	if (negativ)
		g<<"Ciclu negativ"<<'\n';
	else {
		for (int i=2; i<=N; i++)
			g<<D[i]<<" ";
		g<<'\n';
	}
	return 0;
}