#include <fstream>

using namespace std;

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

const long long INFINIT = INT64_MAX - 1;
const int NMAX = 50005;
const int MMAX = 250005;

long long dist[NMAX];
int edges[MMAX][3]; 
int N, M;
bool ciclu_negativ = false;

void citire()
{
	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		fin >> edges[i][0];
		fin >> edges[i][1];
		fin >> edges[i][2];
	}
}

void bellmanford()
{
	for (int i = 1; i <= N; i++)
		dist[i] = INFINIT;
	dist[1] = 0;

	for(int i = 1; i <= N - 1; i++)
		for (int j = 0; j < M; j++)
		{
			int u = edges[j][0];
			int v = edges[j][1];
			long long cost = edges[j][2];
			if (dist[v] > dist[u] + cost)
				dist[v] = dist[u] + cost;
		}
		
	for (int j = 0; j < M; j++)
	{
		int u = edges[j][0];
		int v = edges[j][1];
		long long cost = edges[j][2];
		if (dist[v] > dist[u] + cost)
			ciclu_negativ = true;
	}
}

int main()
{
	citire();
	bellmanford();
	if (ciclu_negativ)
		fout << "Ciclu negativ!";
	else
		for (int i = 2; i <= N; i++)
			fout << dist[i] << ' ';
	return 0;
}