#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>

typedef std::vector<std::vector<std::pair<int, int>>> adj_list_t;

std::vector<int> BellmanFordMoore(adj_list_t &adjList, int nodeStart)
{
	std::vector<int> distance(adjList.size());
	const int INF = std::numeric_limits<int>::max();

	for (int i = 0; i < distance.size(); i++)
		distance[i] = INF;

	distance[nodeStart] = 0;

	size_t numVertices = adjList.size();

	// at most |V| - 1 relaxations needed
	for (size_t i = 0; i < numVertices - 1; i++) {
		for (size_t j = 0; j < numVertices; j++) {
			for (auto edge : adjList[j])
			{
				int from = j;
				int to = edge.first;
				int cost = edge.second;

				if (distance[from] == INF || cost == INF) continue;

				if (distance[to] > distance[from] + cost)
				{
					distance[to] = distance[from] + cost;
				}
			}
		}
	}

	// negative cycle
	for (size_t j = 0; j < numVertices; j++) {
		for (auto edge : adjList[j])
		{
			int from = j;
			int to = edge.first;
			int cost = edge.second;

			if (distance[from] == INF || cost == INF) continue;

			if (distance[to] > distance[from] + cost)
			{
				throw std::runtime_error("Negative cycle detected!");
			}
		}
	}

	return distance;
}

int main(void)
{
	std::ifstream in("bellmanford.in");
	size_t N, M;
	in >> N >> M;
	adj_list_t adjList(N);

	for (size_t i = 0; i < M; i++)
	{
		int from, to, cost;
		in >> from >> to >> cost;
		adjList[from-1].push_back({ to-1,cost });
	}

	std::vector<int> distance;

	std::ofstream out("bellmanford.out");

	try
	{
		distance = BellmanFordMoore(adjList, 0);

		for (size_t i = 1; i < distance.size(); i++)
			out << distance[i] << ' ';
	}
	catch (std::exception &ex) {
		out << "Ciclu negativ!";
	}


	in.close();
	out.close();

	return 0;
}