#include <fstream>
#include <vector>
#include <tuple>
#include <limits>
#include <algorithm>

using Vertex = int;
using Distance = int64_t;

using Edge = std::tuple<Vertex, Vertex, Distance>;

bool BellmanFord(std::vector<Distance>& distances, const std::vector<Edge>& graph, int N)
{
	std::vector<int> relax(N, 0);
	for (auto i = 0; i < N; ++i)
	{
		auto changed = false;
		for (const auto& edge : graph)
		{
			Vertex u, v;
			Distance d;
			std::tie(u, v, d) = edge;
			if ((distances[u - 1] + d) < distances[v - 1])
			{
				++relax[v - 1];
				changed = true;
				distances[v - 1] = distances[u - 1] + d;
				if (relax[v - 1] == N)
					return true;
			}
		}
		if (!changed)
			return false;
	}

	for (const auto& edge : graph)
		{
			Vertex u, v;
			Distance d;
			std::tie(u, v, d) = edge;
			if ((distances[u - 1] + d) < distances[v - 1])
			{
				return true;
			}
		}
	return false;
}
int main()
{
	std::ifstream fin("bellmanford.in");
	int N, M;
	fin >> N >> M;
	std::vector<Distance> distances(N, std::numeric_limits<Distance>::max() - 1001);
	std::vector<Edge> edges(M);
	for (int i = 0; i < M; ++i)
	{
		Vertex u, v;
		Distance d;
		fin >> u >> v >> d;
		edges[i] = std::make_tuple(u, v , d);
	}
	fin.close();
	distances[0] = 0;
	std::ofstream fout("bellmanford.out");
	auto negatives = BellmanFord(distances, edges, N);
	if (negatives)
	{
		fout << "Ciclu negativ!";
		fout.close();
		return 0;
	}
	distances.erase(distances.begin());
	for (const auto d : distances)
	{
		fout << d << " ";
	}
	fout.close();
	return 0;
}