#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits>
#include <stdexcept>

typedef int cost_t;
typedef unsigned int vertex_t;
typedef std::pair<vertex_t,cost_t> edge_t;

// Shortest Path Faster Algorithm
std::vector<cost_t> SPFA(std::vector<std::vector<edge_t>> &edges, size_t numVertices, vertex_t startVertex)
{
	const int INF = std::numeric_limits<int>::max();
	std::vector<cost_t> distance(numVertices, INF);

	// distance to start vertex is 0
	distance[startVertex] = 0;

	std::queue<vertex_t> Q;

	// keep track of the vertices that are in the queue
	std::vector<bool> inQueue(numVertices,false);

	// keep track of how many times a vertex has been processed
	std::vector<size_t> countQueue(numVertices,0);

	// add the start vertex to the queue
	Q.push(startVertex);

	inQueue[startVertex] = true;

	while (!Q.empty())
	{
		// get the next vertex
		vertex_t currVertex  = Q.front();
		
		// remove it from the queue
		Q.pop();

		inQueue[currVertex] = false;

		// relax
		for (auto it = edges[currVertex].begin(); it != edges[currVertex].end(); it++)
		{
			vertex_t to = it->first;
			cost_t cost = it->second;
			
			if (distance[currVertex] == INF || cost==INF) continue;

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

				if (!inQueue[to])
				{
					if (countQueue[to] > numVertices) {
						throw std::runtime_error("Negative cycle!");
					}

					Q.push(to);
					inQueue[to] = true;
					countQueue[to]++;
				}

			}
		}
	}

	return distance;
}

int main(void)
{
	std::ifstream in("bellmanford.in");

	size_t N, M;
	in >> N >> M;

	std::vector<std::vector<edge_t>> edges(M);

	// read the edges
	for (size_t i = 0; i < M; i++)
	{
		vertex_t from, to;
		cost_t cost;

		in >> from >> to >> cost;

		edges[from - 1].push_back({ to - 1 ,cost });
	}

	in.close();

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

	try
	{
		std::vector<cost_t> dist = SPFA(edges, N, 0);

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

	out.close();


	return 0;
}