#include<stdio.h>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;

#define max 50005
#define inf 0x3f3f3f3f
vector< pair<int,int> > roads[max];
int n,m,cnt[max],d[max];
bool is_queue[max];
queue<int> Q;
bool ciclu;
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);
		roads[x].push_back( make_pair(y,c) );
	}

	ciclu=false;
	memset(d,inf,sizeof(d));
	is_queue[1]=1;
	Q.push(1);
	d[1]=0;
	while (!Q.empty() && !ciclu)
	{
		int x=Q.front();
		Q.pop();
		is_queue[x]=0;
		for(vector< pair<int,int> >::iterator it=roads[x].begin(); it!=roads[x].end();it++)
		{
			if(d[x]<inf)
				if(d[x]+(it->second)<d[it->first])
				{
					d[it->first]=d[x]+it->second;
			if(!is_queue[it->first])
			{
				if(cnt[it->first]>n)
					ciclu=true;
				else
				{
					Q.push(it->first);
					is_queue[it->first]=1;
					cnt[it->first]++;
				}
			}
				}
		}

	}
	if(ciclu==true)
		printf("Ciclu negativ!");
	else
		for(int i=2;i<=n;i++)
			printf("%d ",d[i]);
}