#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

struct myComp {
	constexpr bool operator()(
		pair<int, int> const& a,
		pair<int, int> const& b)
		const noexcept
	{
		return a.first > b.first;
	}
};


void dijkstra(std::vector<std::vector<std::pair<int, int>>> graph, int no_of_vertices)
{
	vector<int> distances_to_vertices(no_of_vertices + 1, INT_MAX);
	vector<bool> visited_vertices(no_of_vertices + 1, false);
	priority_queue<pair<int, int>, vector<pair<int, int>>, myComp> utility_heap;

	distances_to_vertices[1] = 0;
	utility_heap.emplace(distances_to_vertices[1], 1);

	while (!utility_heap.empty())
	{
		int vertice = utility_heap.top().second;
		utility_heap.pop();
		if (!visited_vertices[vertice])
		{
			visited_vertices[vertice] = true;

			int i = 0;
			if (graph[vertice].size() > 0)
			{
				while (i < graph[vertice].size())
				{
					if (distances_to_vertices[vertice] + graph[vertice][i].first < distances_to_vertices[graph[vertice][i].second])
					{
						distances_to_vertices[graph[vertice][i].second] = distances_to_vertices[vertice] + graph[vertice][i].first;
					}
					utility_heap.emplace(distances_to_vertices[graph[vertice][i].second], graph[vertice][i].second);
					i++;
				}
			}
		}
	}

	for (int i = 2; i <= no_of_vertices; i++)
	{
		if (distances_to_vertices[i] == INT_MAX) {
			fout << 0 << " ";
		}
		else
		{
			fout << distances_to_vertices[i] << " ";;
		}
	}

}

void add_edges(std::vector<std::vector<std::pair<int, int>>>& graph, int no_of_edges)
{
	int from_vertex{ 0 };
	int to_vertex{ 0 };
	int weight{ 0 };

	for (int i = 1; i <= no_of_edges; i++)
	{
		fin >> from_vertex >> to_vertex >> weight;
		graph[from_vertex].push_back({ weight, to_vertex });
	}
}

int main() {

	int no_of_vertices{ 0 };
	int no_of_edges{ 0 };

	fin >> no_of_vertices;
	fin >> no_of_edges;

	std::vector<std::vector<std::pair<int, int>>> graph(no_of_vertices + 1);

	add_edges(graph, no_of_edges);
	dijkstra(graph, no_of_vertices);

	return 0;
}