#include <stdio.h>
#include <queue>
#include <vector>
#include <utility>
#include <list>
#include <climits>

#define INF INT_MAX

using namespace std;

typedef pair<int, int> Node;

class costPriority {

  public:
  	bool operator()(const Node& left_node, const Node& right_node) {
       	return left_node.second > right_node.second;
  	}	
};

int main() {


	FILE* fin;
	FILE* fout;

	fin = fopen("dijkstra.in", "r");
	fout = fopen("dijkstra.out", "w");

	int n, m;

	fscanf(fin, "%d%d", &n, &m);
	
	vector<vector<Node>> graph(n + 1);
	vector<int> distance(n + 1, INF);
	vector<bool> select(n + 1, false);

	priority_queue<Node, vector<Node>, costPriority> node_queue;

	int x, y, cost;

	for(int i = 0; i < m; i++) {
		fscanf(fin, "%d%d%d", &x, &y, &cost);
		graph[x].push_back(make_pair(y, cost));
	}

	select[1] = true;
	int expanded = 1;


	for (unsigned int j = 0; j < graph[1].size(); j++) {
		distance[graph[1][j].first] = min(distance[graph[1][j].first], graph[1][j].second);
		node_queue.push(graph[1][j]);
	}

	while(!node_queue.empty()) { //} && expanded < n) {
		Node intermediary = node_queue.top();
		node_queue.pop();

		x = intermediary.first;

		if(select[x])
			continue;

		for(unsigned int neighbor = 0; neighbor < graph[x].size(); neighbor++)
		{
			y = graph[x][neighbor].first;
			cost = graph[x][neighbor].second;


			if(distance[y] > distance[x] + cost) {
				node_queue.push(make_pair(y, distance[x] + cost));
				distance[y] = distance[x] + cost;
			}
		}

		select[x] = true;
		expanded++;

	}

	for(unsigned int i = 2; i <= n; i++) {
		fprintf(fout, "%d ", distance[i]);
	}

	fclose(fin);
	fclose(fout);
	return 0;

}