#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>

#define INPUT_FILE_NAME "dijkstra.in"
#define OUTPUT_FILE_NAME "dijkstra.out"
#define N_MAX 50000

struct Muchie {

	int dest, cost;
	Muchie (int dest, int cost);

};

Muchie::Muchie (int _dest, int _cost) {
	dest = _dest;
	cost = _cost;
}

struct Graf {

	int n, m;
	std::vector <Muchie> a[N_MAX];

};

Graf *g = new Graf();
int d[N_MAX], p[N_MAX];
bool viz[N_MAX];

void read_file () {
	
	std::fstream fin (INPUT_FILE_NAME, std::ios::in);
	fin >> g->n;
	fin >> g->m;
	int src, dest, cost;
	
	while (fin >> src >> dest >> cost) {
		g->a[src].push_back (Muchie (dest, cost));
		//(g->m) ++;
	}

	fin.close ();
}

void print_graf () {
	
	std::cout << "N = "<< g->n << " M = " << g->m << '\n';
	
	for (int i = 1; i <= g->n; i++) {
	
		std::cout << i << ": ";
		for (std::vector<Muchie>::iterator it = g->a[i].begin(); it != g->a[i].end(); it++) {
			std::cout << it->dest << " - " << it->cost << "; ";
		}

		std::cout << '\n';
	}

}

struct compare {

	bool operator()(const int& l, const int& r) {

		return d[l] > d[r];

	}

}; 


void path (int x) {

	if (p[x] != 0) {
		path (p[x]);
		std::cout << x << " ";
	} else {
		std::cout << x << " ";
	}

}

void dijkstra (int s) {

	std::priority_queue <int, std::vector <int>, compare> pq;	
	
	for (int i = 1; i <= g->n; i++) {

		d[i] = INT_MAX;
		p[i] = 0;
		viz[i] = false;

	}

	d[s] = 0;
	for (int i = 1; i <= g->n; i++) {
		pq.push (i);
	}

	while (!pq.empty()) {
		
		int u = pq.top();
		pq.pop();
		viz[u] = true;

		for (std::vector<Muchie>::iterator it = g->a[u].begin(); it != g->a[u].end(); it++) {

			if (!viz[it->dest] && u != it->dest && d[u] != INT_MAX && d[it->dest] > d[u] + it->cost) {
				
				d[it->dest] = d[u] + it->cost;
				p[it->dest] = u;
				pq.push (it->dest);

			}

		}

	}

	std::fstream fout (OUTPUT_FILE_NAME, std::ios::out);

	for (int i = 2; i <= g->n; i++) {
		fout << d[i] << " ";
	}


	/*for (int i = 1; i <= g->n; i++) {
		std::cout << s << " - " << i << " cost : " << d[i] << "path : ";
		path (i);
		std::cout << "\n";
	}*/

}


int main (void) {

	read_file ();
	dijkstra (1);
	return 0;

}