#include <fstream>
#include <vector>
#include <utility>
#include <queue>

const int MAX_N(50001);
const int MAX_VALUE(1 << 30);

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

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] == MAX_VALUE ? 0 : Dist[i]) << ' ';
	output.put('\n');
	output.close();
}

inline void Dijkstra (void)
{
	for (int i(1) ; i <= n ; ++i)
		Dist[i] = MAX_VALUE;
	Dist[1] = 0;
	Heap.emplace(1,0);
	int node, cost;
	while (!Heap.empty())
	{
		node = Heap.top().first;
		cost = Heap.top().second;
		Heap.pop();
		if (Dist[node] != cost)
			continue;
		for (auto it : Graph[node])
			if (cost + it.second < Dist[it.first])
			{
				Dist[it.first] = cost + it.second;
				Heap.emplace(it.first,cost + it.second);
			}
	}
}

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