#include <cstddef>
#include <fstream>
#include <limits>
#include <memory>
#include <set>
#include <vector>
#include <utility>

template <typename T>
class TemporaryAllocator : public std::allocator<T>
{
public:
	typedef std::size_t size_type; 
	typedef std::ptrdiff_t difference_type;
	typedef T* pointer;
	typedef const T* const_pointer;
	typedef T& reference;
	typedef const T& const_reference;
	typedef T value_type;

	template <typename U>
	struct rebind
	{
		typedef TemporaryAllocator<U> other;
	};
 
	TemporaryAllocator()
	{

	}

	TemporaryAllocator(TemporaryAllocator const&)
	{

	}

	template<typename U>
	TemporaryAllocator(TemporaryAllocator<U> const&)
	{

	}

	~TemporaryAllocator()
	{

	}

	pointer address(reference r)
	{
		return &r;
	}

	const_pointer address(const_reference r)
	{
		return &r;
	}

	pointer allocate(size_type cnt, typename std::allocator<void>::const_pointer = 0)
	{
		std::pair<T*, ptrdiff_t> result = std::get_temporary_buffer<T>(cnt);

		return result.first;
	}

	void deallocate(pointer p, size_type)
	{
		std::return_temporary_buffer(p);
	}

	size_type max_size() const
	{
		return std::numeric_limits<size_type>::max() / sizeof(T);
	}

	void construct(pointer p, const T& t)
	{
		new(p) T(t);
	}

	void destroy(pointer p)
	{
		p->~T();
	}

	bool operator ==(TemporaryAllocator const&)
	{
		return true;
	}

	bool operator !=(TemporaryAllocator const& a)
	{
		return !(*this == a);
	}
};

int main()
{
	std::ifstream in("dijkstra.in");
	std::ofstream out("dijkstra.out");

	std::vector<std::vector<int, TemporaryAllocator<int> > > arcs, graph;
	
	int nodeCount, arcCount;
	in >> nodeCount >> arcCount;

	graph.resize(arcCount);
	arcs.resize(arcCount);

	for (int i = 1; i <= arcCount; i++)
	{
		int sourceNode, targetNode, arcLength;
		in >> sourceNode >> targetNode >> arcLength;

		graph.at(sourceNode).push_back(targetNode);
		arcs.at(sourceNode).push_back(arcLength);
	}

	std::vector<int, TemporaryAllocator<int> > distances(nodeCount + 1, std::numeric_limits<int>::max());
	std::set<std::pair<int, int> > targets;
	targets.insert(std::make_pair(0, 1));

	while (targets.size() > 0)
	{
		int origDist = (*targets.begin()).first;
		int origNode = (*targets.begin()).second;

		targets.erase(targets.begin());

		for (int i = 0; i < static_cast<int>(graph.at(origNode).size()); i++)
		{
			int arc = arcs.at(origNode).at(i);
			int node = graph.at(origNode).at(i);

			if (distances.at(node) > origDist + arc)
			{
				distances.at(node) = origDist + arc;
				
				targets.insert(std::make_pair(distances.at(node), node));
			}
		}
	}

	// Output the results.
	for (int i = 2; i <= nodeCount; i++)
		out << ((distances.at(i) == std::numeric_limits<int>::max()) ? 0 : distances.at(i)) << ' ';
}