#include<stdio.h>
#include<vector>
#include<list>
using namespace std;
FILE*f=fopen("bellmanford.in","r");
FILE*g=fopen("bellmanford.out","w");
int n,m,x,y,c,nr,d[50001],s[50001];
char viz[50001];
vector <pair<int,int> > v[50001];
list <int> w;
int main()
{
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&x,&y,&c);
		v[x].push_back (make_pair(y,c));
	}
	
	
	for(int i=2;i<=n;++i)
		d[i]=2000000000;
	
	int ok=1;
	w.push_back (1);
	viz[1]=1;
	int k=1;
	while(k&&w.size())
	{
		int nod=*w.begin();
		for(int i=0;i<v[nod].size();++i)
		{
			if(d[v[nod][i].first]>d[nod]+v[nod][i].second)
			{
				if(!viz[v[nod][i].first])
				{
					w.push_back (v[nod][i].first);
					viz[v[nod][i].first]=1;
				}
				d[v[nod][i].first]=d[nod]+v[nod][i].second;
				s[v[nod][i].first]++;
				if(s[v[nod][i].first]==n)
				{
					k=0;
					break;
				}
				
			}
		}
		viz[nod]=0;
		w.pop_front();
	}
	
	if(!k)
		fprintf(g,"Ciclu negativ!");
	else
		for(int i=2;i<=n;++i)
			fprintf(g,"%d ",d[i]);
	
	
	fclose(g);
	fclose(f);
	return 0;
}