#include <iostream>
#include <fstream>
#include <list>
#include <queue>

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

#define INF (1 << 30) - 1

struct Node {
public:
	int destination; //to where
	int cost; //to what cost

	Node(int destination, int cost) :destination(destination), cost(cost) {}

	friend std::ostream& operator<<(std::ostream& os, const Node& node);
	
};

std::ostream& operator<<(std::ostream& os, const Node& node)
{
	os << node.destination << " cu costul: " << node.cost << '\n';
	return os;
}

class Graph {
	int m_vertices;

	std::list<Node>* adjList;

public:
	Graph(int vertices) : m_vertices(vertices)
	{
		adjList = new std::list<Node>[m_vertices + 1];
	}

	void AddEdge(int source, int destination, int cost)
	{
		adjList[source].push_back(Node(destination, cost));
	}

	void Dijkstra(int start);

	void PrintGraph()
	{
		for (int i = 1; i <= m_vertices; i++)
		{
			std::cout << "Nodul cu nr." << i << " are vecinii:" << "\n\t";
			for (auto it = adjList[i].begin(); it != adjList[i].end(); it++)
			{
				std::cout << "->" << (*it) << '\t';
			}
			std::cout << '\n';
		}

	}

};

struct Comparator {
	bool operator()(const Node& a, const Node& b)
	{
		return a.cost > b.cost;
	}
};

void Graph::Dijkstra(int start)
{
	std::priority_queue<Node, std::vector<Node>, Comparator> MinHeap;

	std::vector<int> distances(m_vertices + 1, INF);
	std::vector<bool> visited(m_vertices + 1, false);
	
	MinHeap.push(Node(start, 0));
	distances[start] = 0;

	while (!MinHeap.empty())
	{
		int src = MinHeap.top().destination;
		MinHeap.pop();

		visited[src] = true;

		std::list<Node>::iterator it;
		for (it = adjList[src].begin(); it != adjList[src].end(); it++)
		{
			int dest = it->destination;
			int cost = it->cost;

			int CostSalt = distances[src] + cost

			if (distances[dest] > CostSalt)
			{
				distances[dest] = CostSalt;
				if(visited[dest] == false)
					MinHeap.push(Node(dest, CostSalt));
			}
		}
	}
	/*std::cout << "Distance from vertex " << start << " to:\n";
	for (int i = 1; i <= m_vertices; i++)
	{
		std::cout << "\tVertex " << i << " is " << distances[i] << '\n';
	}*/
	for (int i = 2; i <= m_vertices; i++)
	{
		if (distances[i] == INF)
			out << "0 ";
		else
			out << distances[i] << " ";
	}

}

int main()
{	
	int vertices{ 0 }, edges{ 0 };
	in >> vertices >> edges;

	Graph MyGraph(vertices);
	int src{ 0 }, dest{ 0 }, cost{ 0 };
	for (int i = 0; i < edges; i++)
	{
		in >> src >> dest >> cost;
		MyGraph.AddEdge(src, dest, cost);
	}
	MyGraph.Dijkstra(1);
	return 0;
}