#include <algorithm>
#include <bitset>
#include <climits>
#include <fstream>
#include <iterator>
#include <queue>
#include <vector>
#include <utility>

void mainBellman()
{
	std::ifstream in("bellmanford.in");
	
	int nodeCount, arcCount;
	in >> nodeCount >> arcCount;
	
	std::vector<std::vector<std::pair<int, int> > > graph(nodeCount + 1);
	
	std::vector<int> destinations(nodeCount + 1, INT_MAX);
	destinations[1] = 0;

	for (int i = 0; i < arcCount; i++)
	{
		int source, destination, length;
		in >> source >> destination >> length;

		graph[source].push_back(std::make_pair(destination, length));
	}

	std::bitset<50001> isInHeap;
	isInHeap[1] = true;

	std::vector<int> nr(nodeCount + 1, 0);
	nr[1] = 1;

	std::queue<int> queue;

	for (queue.push(1); !queue.empty(); queue.pop())
	{
		int source = queue.front();
		isInHeap[source] = false;

		for (std::vector<std::pair<int, int> >::iterator i = graph[source].begin(); i != graph[source].end(); i++)
		{
			int dest = i->first;
			int length = i->second;

			if (destinations[dest] > destinations[source] + length)
			{
				destinations[dest] = destinations[source] + length;

				if (!isInHeap[dest])
				{
					queue.push(dest);

					isInHeap[dest] = true;
				}

				if (nr[dest]++ > nodeCount)
				{
					std::ofstream out("bellmanford.out");
					out << "Ciclu negativ!";

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

	std::copy(destinations.begin() + 2, destinations.end(), std::ostream_iterator<int>(out, " "));
}


int main()
{
	mainBellman();
}