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

using namespace std;

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

const long long INFINIT = INT32_MAX;
const int NMAX = 50005;

long long dist[NMAX];
vector < pair <int, int> > weighted_edges[NMAX];
queue < int > nodes;
bool inqueue[NMAX];
int aparitii[NMAX];

int N, M;
bool ciclu_negativ = false;

void citire()
{
	fin >> N >> M;
	int x, y, z;
	for (int i = 0; i < M; i++)
	{
		fin >> x >> y >> z;
		weighted_edges[x].push_back( {y, z} );
	}
}

void bellmanford()
{
	for (int i = 1; i <= N; i++)
		dist[i] = INFINIT;
	dist[1] = 0;
	nodes.push(1);
	inqueue[1] = true;

	while(!nodes.empty() && !ciclu_negativ)
	{
		int top = nodes.front();
		for(unsigned int i = 0; i < weighted_edges[top].size(); i++)
		{
			int u = top;
			int v          = weighted_edges[top][i].first;
			long long cost = weighted_edges[top][i].second;
			if (dist[v] > dist[u] + cost)
			{
				dist[v] = dist[u] + cost;
				if (!inqueue[v])
				{
					nodes.push(v);
					inqueue[v] = true;
				}
				aparitii[v]++;
				if (aparitii[v] == N)
					ciclu_negativ = true;
			}		
		}
		nodes.pop();
		inqueue[top] = false;
	}
}

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