#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <bitset>
#define INF 0x7f7f7f7f
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;
bitset<50001> is_visited;

/*
	Coada cu prioritate va ordona nodurile stocate in ea, in ordine crescatoare d.p.d.v. al costului. 
	Pare ca, coada cu prioritate ar salva nodurile in ordine descrescatoare, dar cand trebuie inserat costul nodului in coada,
	eu introduc costul cu un "-" in fata. Deci daca am avea costurile 2 si 9, intr-o coada cu prioritate, prima data s-ar stoca
	nodul cu costul 9, iar apoi nodul cu costul 2. Dar, avand in vedere ca eu salvez costurile cu un "-" in fata, atunci costurile devin:
	-2 si -9, de data aceasta, codul cu costul -2 fiind stocat primul in coada cu prioritate, iar apoi, nodul cu costul -9.
	Procedura asta a fost folosita pentru a nu fi nevoie sa definesc un comparator, care sa ordoneze nodurile, in ordine crescatoare
	in functie de costul lor.
	Motivul, pentru care este nevoie ca nodurile sa fie stocate in ordine crescatoare, in functie de costul lor este urmatorul:
		in momentul in care ajung sa vizitez un nod, am certitudinea ca pana in acel moment, am gasit cel mai scurt drum pana la acel nod.

*/
void dijkstra_traversal() {
	memset(distances, INF, sizeof distances);
	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();
		is_visited[current_node] = true;
		neighbors.pop();
		for (int i = 0; i < current_nr_neighbors; ++i) {
			int neighbor = weighted_graph[current_node][i].first;
			if (!is_visited[neighbor]) {
				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;
}