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

using namespace std;
int INF = (1 << 30) - 1;

class Graph
{
private:
	int n, m;
	vector<vector<pair<int, int>>> adj_list_costs; //A vector with the neighbours of all the nodes and the cost of the edges between them
	vector<vector<int>> adj_list; //A vector with the neighbours of all the nodes 
public:
	Graph(int nodes, int edges);
	void add_edge_cost(int parent, int child, int cost);
	void add_edge(int parent, int child);
	int hamilton();
	vector<int> dijkstra();
	vector<int> euler_circuit();
};

Graph::Graph(int nodes_no, int edges_no) // Initiate the values of the graph
{
	n = nodes_no;
	m = edges_no;
	adj_list_costs.resize(nodes_no + 1);
	adj_list.resize(nodes_no + 1);
}

void Graph::add_edge_cost(int parent, int child, int cost) // Adding edges and their costs in the adjacency list
{
	adj_list_costs[parent].push_back(make_pair(child, cost));
}

void Graph::add_edge(int parent, int child) // Adding edges in the adjacency list
{
	adj_list[parent].push_back(child);
}

int Graph::hamilton() // Minimum Flow Cost Hamiltonian Cycle
{
	int final_cost = INF; // The final cost of the Hamiltonian Cycle
	int nodes_no = 1 << n;
	vector<vector<int>> costs; // costs[i][j] of minimal costs between 0 and a node j that
							   // contains exactly the nodes used in binary representation of i
	costs.resize(nodes_no);
	for (int i = 0; i < nodes_no; i++)
		for (int j = 0; j < n; j++)
			costs[i].push_back(INF);
	costs[1][0] = 0; // Let the cycle begin form the 0, so the cycle with only the node 0 has a cost of 0
	for (int i = 0; i < nodes_no; i++) // i gives the nodes of the chain
		for (int j = 0; j < n; j++)
			if ((1 << j) & i) // Check if the node is a part of the chain described by i's binary representation
			{
				for (int k = 0; k < adj_list_costs[j].size(); k++)  // Get through all the neighbours of the node
				{

					if (i & (1 << adj_list_costs[j][k].first))  // Check if the neighbour node is a part of the chain
					{ 
						// Actualise the minum cost - check if using the neighbouring node will get a better cost
						costs[i][j] = min(costs[i][j], costs[i ^ (1 << j)][adj_list_costs[j][k].first] +
							adj_list_costs[j][k].second);
					}
				}
			}

	for (int i = 0; i < adj_list_costs[0].size(); ++i)
		final_cost = min(final_cost, costs[nodes_no - 1][adj_list_costs[0][i].first] +
			adj_list_costs[0][i].second);
	return final_cost;
}

vector<int> Graph::euler_circuit()
{
	vector<int> euler_list;
	for(int i=1; i<=n; i++) // Check the first condition for the graph to be eulerian: all its nodes must have an even number of neighbours
		if (adj_list_costs[i].size() % 2 == 1)
		{
			euler_list.push_back(-1);
			return euler_list;
		}
	vector<int> erased;
	erased.resize(m);
	for (int i = 1; i <= m; i++)
		erased.push_back(0);
	stack<int> aux;
	aux.push(1); // Add the beginning node in the cycle
	while (aux.empty() == false)
	{
		int node = aux.top();
		if (adj_list_costs[node].empty() == false)
		{
			pair<int, int> edge = adj_list_costs[node].back(); // Take the edge and its orderd no so that i can erase it from the list
			adj_list_costs[node].pop_back();
			if (erased[edge.second] == 0) // Mark the erased edges
			{
				aux.push(edge.first);
				erased[edge.second] = 1;
			}
		}
		else
		{
			euler_list.push_back(node);
			aux.pop();
		}
	}
	return euler_list;
}

vector<int> Graph::dijkstra()
{
	vector<int>distances(n + 1, 1000000);
	priority_queue<pair<int, int>> pq; //with the use of a priority queue, I simulate a max heap(all the elements will pe in a descending order)
	pq.push(make_pair(0, 1));          //and I'll always take the element from the tail
	distances[1] = 0; //the cost of the soruce code is equal with 0
	while (pq.empty() == false)
	{
		int source = pq.top().second;
		//cout << source;
		pq.pop();
		for (size_t k = 0; k < adj_list_costs[source].size(); k++) //check whether the road through an intermidiate node is shorter than the actual one
		{                                                 //if so, add the new value in distances
			pair<int, int> j = adj_list_costs[source][k];
			int destination = j.first;
			int cost = j.second;
			//cout << destination << " " << cost << endl;
			if (distances[source] + cost < distances[destination]) //if the value trhough an intermidiate node is shorter then the acual one, change the value
			{
				distances[destination] = distances[source] + cost;
				//cout << distances[destination] << endl;
				pq.push(make_pair(-distances[destination], destination)); // introduce the distance as negative integers, so the will be at the end of the pq
			}
		}
	}
	return distances;
}

int main()
{
	/*
	// Minimum Flow Cost Hamiltonian Cycle - https://www.infoarena.ro/problema/hamilton
	int n, m;

	ifstream in("hamilton.in");
	ofstream out("hamilton.out");

	in >> n >> m;
	Graph g(n, m);
	for (int i = 0; i < m; i++) // Reading each edge with its own cost
	{
		int parent, child, cost;
		in >> parent >> child >> cost;
		g.add_edge_cost(parent, child, cost);
	}
	int final_cost = g.hamilton(); // Check whether there are any Hamiltonian Cycles and return the minimal value found
	if (final_cost != INF)
		out << final_cost;
	else
		out << "Nu exista solutie";
	in.close();
	out.close(); 
	*/
	
	// Eulerian ciurcuit - https://www.infoarena.ro/problema/ciclueuler
	/*int n, m;
	ifstream in("ciclueuler.in");
	ofstream out("ciclueuler.out");
	in >> n >> m;
	Graph g(n, m);
	for (int i = 0; i < m; i++) // Reading each edge and adding its order
	{
		int parent, child;
		in >> parent >> child;
		g.add_edge_cost(parent, child, i+1);
		g.add_edge_cost(child, parent, i+1);
	}
	in.close();
	vector<int> euler_list = g.euler_circuit();
	for (int i = 0; i < euler_list.size(); i++)
	{
		out << euler_list[i]<<" ";
	}
	out.close();*/

	//Djikstra Algorithm - https://www.infoarena.ro/problema/dijkstra
	int n, m;
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	in >> n >> m;
	Graph g(n, m);
	for (int i = 0; i < m; i++) // Reading each edge and adding its order
	{
		int parent, child, cost;
		in >> parent >> child >> cost;
		g.add_edge_cost(parent, child, cost);
	}
	in.close();
	vector<int> result = g.dijkstra();
	for (int i = 2; i <= n; i++)
		if (result[i] == 1000000)
			out << 0 << " ";
		else out << result[i] << " ";
	out.close();
	return 0;
}