#include <fstream>
#include <vector>
#include <queue>
#define INF 1e9 + 5
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

typedef pair<int, int> pair_def;
vector<pair_def> weighted_graph[50001];
priority_queue<pair_def> neighbors;
int distances[50001], nr_nodes, nr_edges;

void dijkstra_traversal() {
	std::fill_n(distances, nr_nodes + 1, INF);
	distances[1] = 0;
	neighbors.push({ 0, 1 });
	while (!neighbors.empty()) {
		int current_node = neighbors.top().second;
		int current_nr_neighbors = weighted_graph[current_node].size();
		neighbors.pop();
		for (int i = 0; i < current_nr_neighbors; ++i) {
			int neighbor = weighted_graph[current_node][i].first;
			int cost = weighted_graph[current_node][i].second;
			if (distances[neighbor] > distances[current_node] + cost) {
				distances[neighbor] = distances[current_node] + cost;
				neighbors.push({- distances[neighbor], neighbor});
			}
		}
	}
}

void print_optimal_distance() {
	for (int i = 2; i <= nr_nodes; ++i) {
		if (distances[i] == INF) {
			fout << 0 << ' ';
		} else {
			fout << distances[i] << ' ';
		}
	}
}

int main() {
	fin >> nr_nodes >> nr_edges;
	int src_node, dest_node, edge_cost;
	for (int edge = 1; edge <= nr_edges; ++edge) {
		fin >> src_node >> dest_node >> edge_cost;
		weighted_graph[src_node].push_back({ dest_node, edge_cost });
	}
	dijkstra_traversal();
	print_optimal_distance();
	return 0;
}