#include <cstdio>
#include <vector>
#define inf 2000000000
using namespace std;
vector <pair <int,int> > succ[50050], pred[50050];
int n,m,p=1,r=1;
int cost[50050],q[250250],vis[50050];
bool ch[50050];
bool k;

void read()
{
	freopen ("bellmanford.in","r",stdin);
	freopen ("bellmanford.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,c;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		succ[x].push_back(make_pair(y,c));
		pred[y].push_back(make_pair(x,c));
	}
	for (int i=2;i<=n;++i)
		cost[i]=inf;
}

void bell()
{
	cost[1]=0;
	q[1]=1;
	ch[1]=1;
	while (p<=r)
	{
		int nod=q[p%m];
		++vis[nod];
		if (vis[nod]>n)
		{
			k=1;
			return;
		}
		for (int i=0;i<succ[nod].size();++i)
			if (cost[succ[nod][i].first]>cost[nod]+succ[nod][i].second)
			{
				cost[succ[nod][i].first]=cost[nod]+succ[nod][i].second;
				if (!ch[succ[nod][i].first])
				{
					ch[succ[nod][i].first]=1;
					++r;
					q[r%m]=succ[nod][i].first;
				}
			}
		++p;
		ch[nod]=0;
	}
}

int main()
{
	read();
	bell();
	if (k)
		printf("Ciclu negativ!");
	else
		for (int i=2;i<=n;++i)
			printf("%d ",cost[i]);
	return 0;
}