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

typedef std::pair<int, int> IntPair;
typedef std::vector<IntPair> IntPairVector;
typedef std::vector<IntPairVector> IntPairMatrix;

std::vector<int> destinations;

class Comparator
{
public:
	bool operator ()(int x, int y)
	{
		return destinations[x] > destinations[y];
	}
};

void mainBellman()
{
	std::ifstream in("bellmanford.in");
	
	int nodeCount, arcCount;
	in >> nodeCount >> arcCount;
	
	IntPairMatrix graph(nodeCount + 1);
	destinations.resize(nodeCount + 1);

	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::fill(destinations.begin(), destinations.end(), INT_MAX);
	destinations[1] = 0;

	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 (IntPairVector::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();
}