#include<iostream>
#include<fstream>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

#define maxn 50010
#define maxm 250010
#define inf 1000000000
#define pb push_back
#define mp make_pair

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

struct muchie
{
	long a,b,c;
} e[maxm];

long i,j,m,n,cost[maxn],f[maxn];
vector <long> v[maxn];
vector < pair<long,long> > h;

void init()
{
	cost[1]=0;
	for(i=2;i<=n;i++)
		cost[i]=inf;
	h.pb(mp(0,1));
	make_heap(h.begin(),h.end());
}

void solve()
{
	pair<long,long> per;
	long nod,poz;
	long long pas=0;
	while(h.size() && pas<=1LL*m*n){
		++pas;
		pop_heap(h.begin(),h.end());
		per=h.back();
		h.pop_back();
		nod=per.second;
		f[nod]=0;
		for(j=0;j<v[nod].size();j++){
			poz=v[nod][j];
			if(cost[e[poz].a]+e[poz].c<cost[e[poz].b]){
				cost[e[poz].b]=cost[e[poz].a]+e[poz].c;
				if(!f[e[poz].b]){
					f[e[poz].b]=1;
					h.pb(mp(-cost[e[poz].b],e[poz].b));
					push_heap(h.begin(),h.end());
				}
			}
		}
	}
}

bool negativ()
{
	for(i=1;i<=m;i++)
		if(cost[e[i].a]+e[i].c<cost[e[i].b])
			return 1;
	return 0;
}

int main()
{
	in>>n>>m;
	for(i=1;i<=m;i++){
		in>>e[i].a>>e[i].b>>e[i].c;
		v[e[i].a].pb(i);
	}
	init();
	solve();
	if(negativ()){
		out<<"Ciclu negativ!\n";
		return 0;
	}
	for(i=2;i<=n;i++)
		out<<cost[i]<<" ";
	return 0;
}