#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <string>
using edge = std::pair<int, int>;

std::vector<int> shortest_path(const std::vector<std::vector<edge>>& graph, const int source)
{
	std::vector<int> distances = std::vector<int>(graph.size(), INT32_MAX);
	std::vector<bool> isInQueue = std::vector<bool>(graph.size(), false);
	std::vector<unsigned int> timesImproved = std::vector<unsigned int>(graph.size(), 0);
	distances[source] = 0;

	std::queue<int> q;
	q.push(source);
	isInQueue[source] = true;
	timesImproved[source]++;

	while (!q.empty())
	{
		int current = q.front();
		q.pop();
		isInQueue[current] = false;

		for (edge i : graph[current])
		{
			int dist = distances[current] + i.second;
			if (distances[i.first] > dist)
			{
				distances[i.first] = dist;
				if (!isInQueue[i.first])
				{
					isInQueue[i.first] = true;
					q.push(i.first);
					timesImproved[i.first]++;
					if (timesImproved[i.first] >= graph.size())
					{
						return std::vector<int>(); //return empty vector if there is a negative cycle
					}
				}
			}
		}
	}
	return distances;
}

int main()
{
	unsigned int nVertices, nArcs, source = 1;
	std::vector<std::vector<edge>> arcs(nVertices + 1);

	std::ifstream fin("bellmanford.in");
	std::ofstream fout("bellmanford.out");
	fin >> nVertices >> nArcs;
	arcs = std::vector<std::vector<edge>>(nVertices + 1);

	for (unsigned int i = 1; i <= nVertices; i++)
	{
		arcs[i] = std::vector<std::pair<int, int>>();
	}

	for (unsigned int i = 0; i < nArcs; i++)
	{
		int v, u, c;
		fin >> v >> u >> c;
		arcs[v].push_back(std::pair<int, int>(u, c));
	}
	fin.close();
	std::vector<int> distances = shortest_path();

	if (distances.size() == 0)
		fout << "Ciclu negativ!";
	fout << distances[2];
	for (int i = 3; i < distances.size(); i++)
		fout << " " << distances[i];

	fout.close();
	return 0;
}