#include<fstream>
#include<vector>
#include<bitset>
#include<utility>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m;
vector< pair<int, int> > adj[50001];
int nodes[50001], heap[50001], poz_in_heap[50001], final_distance[50001];
bitset<50001> finished;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void init() {
	int i;
	for(i = 1; i <= n; i++) {
		nodes[i] = INF;
		heap[i] = i;
		poz_in_heap[i] = i;
		finished[i] = 0;
	}
}

void sift(int p) {
	int child, aux;
	if(2 * p > n) return;
	child = 2 * p;
	if(child + 1 <= n && nodes[heap[child + 1]] < nodes[heap[child]]) {
		child += 1;
	}
	while(nodes[heap[child]] < nodes[heap[p]]) {
		aux = heap[child];
		heap[child] = heap[p];
		heap[p] = aux;

		poz_in_heap[heap[child]] = child;
		poz_in_heap[heap[p]] = p;

		p = child;
		if(2 * p > n) break;
		child = 2 * p;
		if(2 * p + 1 <= n && nodes[heap[2 * p + 1]] < nodes[heap[child]]) {
			child = 2 * p + 1;
		}
	}
}

void percolate(int p) {
	int parent, aux;
	if(p == 1) return;
	parent = p / 2;
	while(parent >= 1 && nodes[heap[parent]] > nodes[heap[p]]) {
		aux = heap[parent];
		heap[parent] = heap[p];
		heap[p] = aux;

		poz_in_heap[heap[p]] = p;
		poz_in_heap[heap[parent]] = parent;

		p = parent;
		parent = p / 2;
	}
}

void dijkstra() {
	// init
	int completed = 0, current, currentVal;
	nodes[1] = 0;
	percolate(poz_in_heap[1]);
	while(++completed <= n) {
		// save the distance to the min node from heap
		current = heap[1];
		final_distance[current] = nodes[current];
		finished[current] = 1;

		currentVal = nodes[current];
		nodes[current] = INF;
		sift(1);

		// relax the neighbours
		for(vector< pair<int, int> >::iterator it = adj[current].begin(); it != adj[current].end(); ++it) {
			if(finished[it->first] == 0 && nodes[it->first] > currentVal + it->second) {
				nodes[it->first] = currentVal + it->second;
				// modify the position in heap
				sift(poz_in_heap[it->first]);
				percolate(poz_in_heap[it->first]);
			}
		}
	}
}

int main() {
	int i, u, v, c;

	fin >> n >> m;
	for(i = 0; i < m; i++) {
		fin >> u >> v >> c;
		adj[u].push_back(make_pair(v, c));
	}
	init();
	dijkstra();
	for(i = 2; i <= n; i++) {
		fout << final_distance[i] << " ";
	}
	return 0;
}