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

struct Comparator {
	bool operator()(const std::pair<int,int>& a, const std::pair<int, int>& b) const 
	{
		return a.second < b.second;  // posibila greseala
	}
};

void Citire(std::unordered_map<int, std::vector<std::pair<int,int>>> & Graph, int& number_of_nodes)
{
	std::ifstream fin("dijkstra.in");
	int nr;
	fin >> number_of_nodes>> nr;
	int came_from, came_to, cost;
	while (fin >> came_from >> came_to >> cost)
	{
		Graph[came_from].emplace_back(came_to, cost);
	}
	fin.close();
}

void Dijkstra(std::unordered_map<int, std::vector<std::pair<int, int>>>& Graph, int& start, std::unordered_map<int, int>& cost_so_far)
{
	std::priority_queue<std::pair<int,int>, std::vector<std::pair<int, int>>, Comparator> q;
	std::unordered_map<int, int> came_from;
	came_from[start] = -1;
	cost_so_far[start] = 0;
	q.emplace(start, 0);
	while (q.empty() == false)
	{
		int current = q.top().first;
		q.pop();
		
		for (auto next : Graph[current])
		{
			int new_cost = cost_so_far[current] + next.second;
			if (cost_so_far.find(next.first) == cost_so_far.end() || new_cost < cost_so_far[next.first])
			{
				came_from[next.first] = current;
				cost_so_far[next.first] = new_cost;
				q.emplace(next.first, new_cost);
			}
		}
	}
}

void Afisare(std::unordered_map<int, int> cost_so_far, int start, int number_of_nodes)
{
	std::ofstream fout("dijkstra.out");
	for (int i = 2; i <= number_of_nodes; i++)
	{
		int current = cost_so_far[i];
		if (current == 0 && i != start) fout << -1 << ' ';
		else fout << current << ' ';
	}
	fout.close();
}

int main()
{
	std::unordered_map<int, std::vector<std::pair<int, int>>> Graph;
	int start, number_of_nodes;
	std::unordered_map<int, int> cost_so_far;
	start = 1;
	Citire(Graph,number_of_nodes);
	Dijkstra(Graph, start, cost_so_far);
	Afisare(cost_so_far,start,number_of_nodes);

	return 0;
}