#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

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

int n, m, D[50010], F[50010];
vector < pair < int, int > > V[50010];
queue < int > Q;

int main()
{
	fin >> n >> m;
	for (int x, y, c, i = 1; i <= m; i++)
	{
		fin >> x >> y >> c;
		V[x].push_back( { y, c } );
	}
	
	memset(D, 127, sizeof(D));
	Q.push(1);
	D[1] = 0;
	
	while (!Q.empty())
	{
		int nod = Q.front();
		Q.pop();
		
		F[nod] ++;
		if (F[nod] == n)
		{
			fout << "Ciclu negativ!\n";
			return 0;
		}
		
		for (vector < pair < int, int > > :: iterator it = V[nod].begin(); it != V[nod].end(); it++)
		{
			if (D[nod] + it->second < D[it->first])
			{
				D[it->first] = D[nod] + it->second;
				Q.push(it->first);
			}
		}
	}
	
	for (int i = 2; i <= n; i++) fout << D[i] << ' ';
	return 0;
}