#include <cstdio>
#include <vector>
using namespace std;

const int MAX_N = 50000;
const int INF = 0x3f3f3f3f;

int n, m;
vector< pair<int, int> > G[MAX_N];
int d[MAX_N];
int heap[MAX_N], heapSize, pos[MAX_N]; // heap starts from index 1

void rise ( int p ) {
	for (int k = p; k > 0; k /= 2) {
		if (d[heap[k]] < d[heap[k/2]]) {
			swap(heap[k], heap[k/2]);
			pos[heap[k]] = k; pos[heap[k/2]] = k/2;
		} else {
			break;
		}
	}
}

void lower ( int p ) {
	for (int k = p; k <= heapSize; ) {
		int left = (k*2 <= heapSize) ? d[heap[k*2]] : INF;
		int right = (k*2+1 <= heapSize) ? d[heap[k*2+1]] : INF;
		if (left <= right && left < d[heap[k]]) {
			swap(heap[k], heap[k*2]);
			pos[heap[k]] = k; pos[heap[k*2]] = k*2;
			k = k*2;
		} else
		if (right < left && right < d[heap[k]]) {
			swap(heap[k], heap[k*2+1]);
			pos[heap[k]] = k; pos[heap[k*2+1]] = k*2+1;
			k = k*2+1;
		} else {
			break;
		}
	}
}

void push ( int idx ) {
	++heapSize;
	heap[heapSize] = idx;
	pos[heap[heapSize]] = heapSize;
	rise(heapSize);
}

void update ( int idx ) {
	rise(pos[idx]);
	lower(pos[idx]);
}

int pop() {
	int ret = heap[0];
	swap(heap[0], heap[heapSize]);
	pos[heap[0]] = 0;
	--heapSize;
	lower(0);
	return ret;
}

void dijkstra() {
	fill(d, d+n, INF);
	d[0] = 0;
	for (int i = 0; i < n; ++i) push(i);
	for (; heapSize > 0; pop()) {
		int top = heap[0];
		for (vector< pair<int, int> >::iterator it = G[top].begin(); it != G[top].end(); ++it) {
			if (d[it->first] > d[top] + it->second) {
				d[it->first] = d[top] + it->second;
				update(it->first);
			}
		}
	}
}

int main() {
	freopen("dijkstra.in","rt",stdin);
	freopen("dijkstra.out","wt",stdout);
	scanf("%d %d", &n, &m);
	for (int i = 0, a, b, c; i < m; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		--a; --b;
		G[a].push_back(make_pair(b, c));
	}
	
	dijkstra();

	for (int i = 1; i < n; ++i)
		printf("%d ",d[i]);
	printf("\n");

	return 0;
}