#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

#define __DIRECTED_GRAPH

using namespace std;

class Graph {
	private: 
		unsigned int V;
		vector< pair<int, int> > *L;

	public:
		Graph(unsigned int V);
		~Graph();
		void addEdge(unsigned int u, unsigned int v, unsigned int cost);
		vector<int> dijkstra(unsigned int start);
};

Graph::Graph(unsigned int V) {
	this->V = V;

	this->L = new vector< pair<int, int> >[V];
}

Graph::~Graph() {
	for (unsigned int i = 0; i < V; ++i) {
		L[i].clear();
	}
	//delete L;
}

void Graph::addEdge(unsigned int u, unsigned int v, unsigned int cost) {
	L[u].push_back(make_pair(v, cost));
	#ifndef __DIRECTED_GRAPH
	L[v].push_back(make_pair(u, cost));
	#endif
}

vector<int> Graph::dijkstra(unsigned int start) {
	priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;

	vector<int> dist(V, numeric_limits<int>::max());

	pq.push(make_pair(0, start));
	dist[start] = 0;
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();

		for (unsigned int i = 0; i < L[u].size(); ++i) {
			int v = L[u][i].first;
			int cost = L[u][i].second;

			if (dist[v] > dist[u] + cost) {
				dist[v] = dist[u] + cost;
				pq.push(make_pair(dist[v], v));
			}
		}
	}

	return dist;
}

int main() {
	ifstream fin("dijkstra.in");
	
	unsigned int V, E;
	fin >> V >> E;
	
	Graph * G = new Graph(V);

	unsigned int u, v, w;
	for (unsigned int i = 0; i < E; ++i) {
		fin >> u >> v >> w;
		G->addEdge(u - 1, v - 1, w);
	}

	fin.close();

	vector<int> dist = G->dijkstra(0);

	ofstream fout("dijkstra.out");
	for (unsigned int i = 1; i < V; ++i) {
		fout << dist[i] << " ";
	}
	fout.close();

	delete G;

	return 0;
}