#include<fstream>
#include<queue>
using namespace std;
#define nmax 50005
#define inf 1<<20
vector< pair<int,int> > g[nmax];
queue<int> q;
int d[nmax],viz[nmax];
int n,m;
typedef struct { int a;int b;int c; } muchie;
muchie e[250005];
void citire ()
{
	ifstream fin ("bellmanford.in");
	fin>>n>>m;
	int i,a,b,c;
	for(i=1;i<=m;i++)
		fin>>a>>b>>c,g[a].push_back(make_pair(b,c)),e[i].a=a,e[i].b=b,e[i].c=c;
	fin.close();
}
void bell (int nod)
{
	int i,x,inc,sf;
	for(i=1;i<=n;i++)
		d[i]=inf;
	q.push(nod);
	d[nod]=0;inc=sf=0;
	while(inc<=sf)
	{
		x=q.front();
		viz[x]=0;
		inc++;
		q.pop();
		for(i=0;i<g[x].size();i++)
			if(d[g[x][i].first]>d[x]+g[x][i].second)
			{
				d[g[x][i].first]=d[x]+g[x][i].second;
				if(!viz[g[x][i].first])
				{
					q.push(g[x][i].first);
					sf++;
					viz[g[x][i].first]=1;
				}
			}
	}
}
long check_negativ()
{
    long i;
	for(i=1; i<=m; i++)
      if(d[e[i].a]+e[i].c<d[e[i].b])
          return 1;
    return 0;
}
void scrie ()
{
	int i;
	ofstream fout("bellmanford.out");
	if(check_negativ())
		fout<<"Ciclu negativ";
	else
		for(i=2;i<=n;i++)
			fout<<d[i]<<' ';
	fout.close();
}
int main ()
{
	citire();
	bell(1);
	scrie();
	return 0;
}