#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int Nmax=1<<16;
vector<pair<int,int> > L[Nmax];
bool ok;
queue<int> Q;
int n,m,f[Nmax],ftot[Nmax],cost[Nmax];
void bf()
{
	int x,nod,cc;
	Q.push(1);
	f[1]=true;
	ftot[1]++;
	while(!Q.empty())
	{
		x=Q.front();
		for(vector<pair<int,int> >::iterator it=L[x].begin();it!=L[x].end();it++)
		{
			nod=it->first;
			cc=it->second;
			if(cost[x]+cc<cost[nod] || cost[nod]==0)
			{
				cost[nod]=cost[x]+cc;
				if(!f[nod])
				{
					Q.push(nod);
					f[nod]=true;
					ftot[nod]++;
					if(ftot[nod]==n)
					{
						ok=true;
						return;
					}
				}
			}
		}
		f[x]--;
		Q.pop();
	}
}
int main()
{
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		L[x].push_back(make_pair(y,c));
	}
	ok=false;
	cost[1]=1;
	bf();
	if(ok==true)
		printf("Ciclu negativ!");
	else
		for(int i=2;i<=n;i++)
			printf("%d ",cost[i]-1);
	return 0;
}