#include <fstream>
#include <vector>
#include <utility>
#include <limits>

const int MAX_N(50001);

int n;
std::vector<std::pair<int,int>> Graph [MAX_N];
int Dist [MAX_N];
int Heap [MAX_N], HeapIndex [MAX_N];

inline void Read (void)
{
	std::ifstream input("dijkstra.in");
	int m, x, y, z;
	input >> n >> m;
	while (m)
	{
		input >> x >> y >> z;
		Graph[x].emplace_back(y,z);
		--m;
	}
	input.close();
}

inline void Print (void)
{
	std::ofstream output("dijkstra.out");
	for (int i(2) ; i <= n ; ++i)
		output << Dist[i] << ' ';
	output.put('\n');
	output.close();
}

inline int Parent (int index)
{
	return index / 2;
}

inline int Left_son (int index)
{
	return index * 2;
}

inline int Right_son (int index)
{
	return index * 2 + 1;
}

inline void DownHeap (int index)
{
	int min(index);
	while (true)
	{
		if (Left_son(index) <= Heap[0] && Dist[Heap[Left_son(index)]] < Dist[Heap[index]])
			min = Left_son(index);
		else
			min = index;
		if (Right_son(index) <= Heap[0] && Dist[Heap[Right_son(index)]] < Dist[Heap[min]])
			min = Right_son(index);
		if (min == index)
			break;
		std::swap(HeapIndex[Heap[index]],HeapIndex[Heap[min]]);
		std::swap(Heap[index],Heap[min]);
		index = min;
	}
}

inline void UpHeap (int index)
{
	int node(Heap[index]);
	while (index > 1 && Dist[node] < Dist[Heap[Parent(index)]])
	{
		std::swap(HeapIndex[node],HeapIndex[Heap[Parent(index)]]);
		Heap[index] = Heap[Parent(index)];
		index = Parent(index);
	}
	Heap[index] = node;
}

inline void PopHeap (void)
{
	HeapIndex[Heap[1]] = 0;
	HeapIndex[Heap[Heap[0]]] = 1;
	Heap[1] = Heap[Heap[0]];
	--Heap[0];
	DownHeap(1);
}

inline void Dijkstra (void)
{
	Heap[0] = n;
	for (int i(1) ; i <= n ; ++i)
	{
		Heap[i] = HeapIndex[i] = i;
		Dist[i] = std::numeric_limits<int>::max();
	}
	Dist[1] = 0;
	int node;
	while (Heap[0])
	{
		node = Heap[1];
		PopHeap();
		for (auto it : Graph[node])
			if (Dist[node] + it.second < Dist[it.first])
			{
				Dist[it.first] = Dist[node] + it.second;
				UpHeap(HeapIndex[it.first]);
			}
	}
}

int main (void)
{
	Read();
	Dijkstra();
	Print();
	return 0;
}