#include<fstream>
#include<vector>
#include<queue>
#define dmax 50003
#define mult 1000000000
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m,nr[dmax];
bool t[dmax];
long long dm[dmax];
struct muchie
{	int v;
	short int cst;
};
vector<struct muchie>g[dmax];
vector<struct muchie>::iterator it;
queue<int>q;

void bellmanford()
{	int i,crt,ok=1;
	for(i=1;i<=n;i++)
		dm[i]=mult;
	dm[1]=0;
	q.push(1);
	t[1]=1;
	nr[1]=1;
	while(!q.empty() && ok )
	{	crt=q.front();
		q.pop();
		t[crt]=0;
		for(it=g[crt].begin();it<g[crt].end();it++)
			if(dm[crt]<mult)
				if( dm[it->v]>dm[crt]+it->cst )
				{	dm[it->v]=dm[crt]+it->cst;
					if(!t[it->v])
					{	if(nr[it->v]>n)
							ok=0;
						else
						{	q.push(it->v);
							t[it->v]=1;
							nr[it->v]++;
						}	
					}	
				}
	}	
	if(!ok)
		out<<"Ciclu negativ!";
	else for(i=2;i<=n;i++)
		out<<dm[i]<<" ";	
}	


int main()
{	int i,a,b,c;
	muchie w;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{	in>>a>>b>>c;
		w.cst=c;
		w.v=b;
		g[a].push_back(w);
	}
	in.close();
	bellmanford();
	out.close();
	return 0;
}