#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 in_queue[N_MAX];

void read_file () {
	
	std::fstream fin (INPUT_FILE_NAME, std::ios::in);
	fin >> g->n >> g->m;
	int src, dest, cost;
	while (fin >> src >> dest >> cost) {
		g->a[src].push_back (Muchie (dest, cost));
	}
	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()(std::pair<int, int> const& l, std::pair <int, int> const& r) {
		return l.second > r.second;
	}

}; 

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 < std::pair <int, int>,
						  std::vector < std::pair <int, int> >,
						  compare > pq;	
	
	for (int i = 1; i <= g->n; i++) {
		d[i] = INT_MAX;
		p[i] = 0;
	}
	d[s] = 0;
	for (int i = 1; i <= g->n; i++) {
		pq.push (std::pair <int, int> (i, d[i]));
		in_queue[i] = true;
	}

	while (!pq.empty()) {
		
		int u = pq.top().first;
		pq.pop();
		in_queue[u] = false;

		for (std::vector<Muchie>::iterator it = g->a[u].begin(); it != g->a[u].end(); it++) {
			if (in_queue[it->dest] && d[it->dest] > d[u] + it->cost) {
				
				d[it->dest] = d[u] + it->cost;
				p[it->dest] = u;
				pq.push (std::pair <int, int> (it->dest, d[it->dest]));

			}

		}

	}

	// afisare
	std::fstream fout (OUTPUT_FILE_NAME, std::ios::out);
	for (int i = 2; i <= g->n; i++) {
		if (d[i] == INT_MAX) {
			fout << "0 ";
		} else {
			fout << d[i] << " ";
		}
	}
	fout.close ();

	/*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;

}