#include <fstream>
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef pair <int, int> iPair;

class DirectedGraph
{
	int noVertices;
	list<pair<int, int>> *adjList;

public: 
	DirectedGraph(int noVertices) 
	{
		this->noVertices = noVertices;
		adjList = new list<iPair>[noVertices + 1];
	}
	
	void addEdge(int src, int dest, int distance)
	{
 		adjList[src].push_back(make_pair(dest, distance));
	}
	
	vector<int> getShortestDistancesFromSource(int source)
	{ 	
		priority_queue< iPair, vector <iPair> , greater<iPair> > pq;

		vector<int> distances(noVertices + 1, INF);
		
		pq.push(make_pair(0, source));
		distances[source] = 0;
		
		while (!pq.empty()) {	
			int u = pq.top().second;
			pq.pop();
			
			list< pair<int, int> >::iterator i;
			for (i = adjList[u].begin(); i != adjList[u].end(); ++i) {
				int v = (*i).first;
				int weight = (*i).second;
				
				if (distances[v] > distances[u] + weight) {
					distances[v] = distances[u] + weight;
					pq.push(make_pair(distances[v], v));
				}
			}
	
		}

		return distances;
	}
	
	~DirectedGraph()
	{
		delete[] adjList;
	}
};

int main() 
{
	ifstream inputStream("dijkstra.in");
	ofstream outputStream("dijkstra.out");
		
	int noVertices, noEdges;
	
	inputStream >> noVertices >> noEdges;
	DirectedGraph graph(noVertices);
	for (int i = 0; i < noEdges; ++i) {
		int src, dest, distance;
		inputStream >> src >> dest >> distance;
		graph.addEdge(src, dest, distance);
	}
	
	auto distances = graph.getShortestDistancesFromSource(1);

	for (int i = 2; i < distances.size(); ++i) outputStream << distances[i] << ' ';
	outputStream << '\n';

	return 0;
}