/*
	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.
	Daca am ajuns sa parcurg toti vecinii nodului curent, voi marca nodul curent ca fiind vizitat.
	Chiar daca voi gasi un drum mai scurt pana la nodul curent, nu il voi mai vizita, voi actualiza doar distanta pana la nodul
	curent.
	Motivul pentru care marchez nodul curent ca fiind vizitat este urmatorul:
		nu are sens sa parcurg de mai multe ori vecinii nodului curent, dat fiind faptul ca, costul pana la fiecare vecin
		plecand de la nodul curent va ramane neschimbat.

	OBS: Distanta de la nodul de start, la fiecare nod in parte, se va actualiza in cazul in care se gaseste o ruta mai scurta,
		 neluand in calcul faptul ca deja distanta pana la unul dintre vecini a fost deja modificata din INF, intr-o valoare mai mica, sau
		 ca distanta pana la unul dintre vecini este nemodificata.
*/

#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;

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();
		neighbors.pop();
		for (int i = 0; !is_visited[current_node] && 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 });
			}
		}
		is_visited[current_node] = true;
	}
}

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;
}