#include <fstream>
#include <vector>
#include <list>
#define nmax 50001
#define INF (1<<30)
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,dist[nmax],use[nmax],ct[nmax];
vector < pair < int, int > > v[nmax];
list <int> coada;
int main()
{
	int m,i,j,x,y,c;
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		v[x].push_back(make_pair(y,c));
	}
	
	coada.push_back(1);
	ct[1]=1;
	for(i=2;i<=n;i++)
		dist[i]=INF;
	
	int ok=1;
	while(!coada.empty() && ok)
	{
		i=*coada.begin();
		for(j=0;j<v[i].size();j++)
		{
			if(dist[i]+v[i][j].second<dist[v[i][j].first])
			{
				dist[v[i][j].first]=dist[i]+v[i][j].second;
				if(!use[v[i][j].first])
				{
					use[v[i][j].first];
					coada.push_back(v[i][j].first);
				}
				ct[v[i][j].first]++;
				if(ct[v[i][j].first]>=n) { ok=0; break; }
			}
		}
		use[i]=0;
		coada.pop_front();
	}
	
	for(i=1;i<=n && ok;i++)
		for(j=0;j<v[i].size();j++)
			if(dist[i]+v[i][j].second<dist[v[i][j].first])
			{
				ok=0; 
				break;
			}
	
	if(ok)
	{
		for(i=2;i<=n;i++)
			g<<dist[i]<<' ';
	}
	else g<<"Ciclu negativ!";
}