#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#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];
int distances[50001];
int nr_nodes, nr_edges;

struct compare_costs {
	constexpr bool operator()(pair<int, int> const& a, pair<int, int> const& b) const noexcept {
		return a.second > b.second;
	}
};

priority_queue<pair_def, vector<pair_def>, compare_costs> neighbors;

void dijkstra_traversal() {
	for (int i = 2; i <= nr_nodes; ++i) {
		distances[i] = INF;
	}
	neighbors.push({ 1, 0 });
	while (!neighbors.empty()) {
		int current_node = neighbors.top().first;
		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({neighbor, distances[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;
}