#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;
	int aux;
	fin >> aux;
	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()(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] && 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 (std::pair <int, int> (it->dest, d[it->dest]));

			}

		}

	}

	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;

}