#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,m,ok[50001],i,j,a,b,c,viz[50001],d[50001],ok1;
struct vertex
{
	int x; int cost;
};
vector <vertex> G[50001];
queue <int> q;
int bellmanford()
{
	q.push(1);
	ok[1]=1;
	viz[1]=1;
	int nod;
	while(!q.empty())
	{
		nod=q.front();
		q.pop();
		for(i=0;i<G[nod].size();i++)
			if(d[nod]+G[nod][i].cost<d[G[nod][i].x])
			{
				d[G[nod][i].x]=d[nod]+G[nod][i].cost;
				viz[G[nod][i].x]++;
				if(viz[G[nod][i].x]==n-1)
				{
					ok1=1;
					break;
				}
				if(ok[G[nod][i].x]==0)
				{
					q.push(G[nod][i].x);
					ok[G[nod][i].x]=1;
				}
			}
			if(ok1==1)
				break;
		ok[nod]=0;
	}
	return 0;
}
			
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	vertex nod;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		nod.x=b;
		nod.cost=c;
		G[a].push_back(nod);
	}
	for(i=2;i<=n;i++)
		d[i]=250000010;
	bellmanford();
	if(ok1==1)
		printf("Ciclu negativ!");
	else
		for(i=2;i<=n;i++)
			printf("%d ",d[i]);
	return 0;
}