#include<fstream>
#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int ciclu,nod,nod2,n,m,i,x,y,z,D[50001],ok[50001],nr[50001];
vector<pair<int,int> > a[50001];
vector<pair<int,int> >::iterator it;
deque<int> Q;

void bellman()
{
	while (!Q.empty())
	{
		nod=Q.front();
		Q.pop_front();
		ok[nod]=0;
		
		for (it=a[nod].begin();it!=a[nod].end();it++)
		{
			nod2=(*it).first;
			if (D[nod]+(*it).second<D[nod2])
			{
				D[nod2]=D[nod]+(*it).second;
				if (nr[nod2]>n)
				{
					out<<"Ciclu negativ!";
					ciclu=1;
					return;
				}
				if (!ok[nod2]) 
				{
					nr[nod2]++;
					Q.push_back(nod2);
				}
				ok[nod2]=1;
			}
		}
	}
}
	
int main()
{
	in>>n>>m;
	
	for (i=1;i<=m;i++)
	{
		in>>x>>y>>z;
		a[x].push_back(make_pair(y,z));
	}
	
	Q.push_back(1);
	for (i=2;i<=n;i++) D[i]=99999;
	ok[1]=1;
	
	bellman();
	
	if (!ciclu)
		for (i=2;i<=n;i++)
			out<<D[i]<<' ';
}