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

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;
	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()(const int& l, const int& r) {

		return d[l] > d[r];

	}

}; 


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

			}

		}

	}
/*
	for (int i = 1; i <= g->n; i++) {
		std::cout << s << " - " << i << " cost = " << d[i] << "\n";
	}
*/
  std::fstream fout (OUTPUT_FILE_NAME, std::ios::out);
    for (int i = 2; i <= g->n; i++) {
        fout << d[i] << " ";
    }
    fout.close ();


}


int main (void) {

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

}