#include <iostream>
#include <fstream>

#define inf 100000
using namespace std;


struct Drum
{
	int x,y,c;
};

int main()
{
	Drum a[35000];
	long val[50001];
	int ciclu[50001];

	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	int n,m;
	fin >> n >> m ;

	for (int i=0;i<m;i++)
		fin >> a[i].x >>a[i].y >> a[i].c;

	for (int i=1; i<=n;i++)
	{
		val[i]=inf;
		ciclu[i]=0;
	}

		val[1]=0;

	bool ok=true;
	unsigned int max=0;
	while (ok) 
	{
		ok = false;
       
		for (int i = m-1; i>=0; i--)
	   {
		   if ((val[a[i].x]+a[i].c) < val[a[i].y] )
		   {
			   ok = true;
			   val[a[i].y] = val[a[i].x] + a[i].c;
			   ciclu[a[i].x] += 1; 
			   if (ciclu[a[i].x]>max) max = ciclu[a[i].x];
		   }
	   }
      
	   if (max > n) {fout << "Ciclu negativ!"; return 0; }
		
	}
	

	for (int i=2;i<=n;i++)
		fout << val[i] << " ";

	fin.close();
	fout.close();
	return 0;
}