#include<cstdio>
#include<vector>
#include<utility>
using namespace std;

int n,m,x,y,c,i,oo=20000000,d[50010];
vector<pair<int,pair<int,int> > > M;

void read(),solve();

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
		scanf("%d%d%d",&x,&y,&c);
		M.push_back(make_pair(x,make_pair(y,c)));
	}
}

void solve()
{
	vector<pair<int,pair<int,int> > >::iterator it;
	d[1]=0;
	for(i=2;i<=n;i++)d[i]=oo;
	for(i=1;i<n;i++)
	{
		for(it=M.begin();it!=M.end();it++)
		{
			x=it->first;y=it->second.first;c=it->second.second;
			if(d[x]+c < d[y])d[y]=d[x]+c;
		}
	}
	for(it=M.begin();it!=M.end();it++)
		{
			x=it->first;y=it->second.first;c=it->second.second;
			if(d[x]+c < d[y]){printf("Ciclu negativ!");return;}
		}
	for(i=2;i<=n;i++)printf("%d ",d[i]);
}