#include <cstdio>

#define MAXN 50005
const int inf = 1 << 30;

using namespace std;

typedef struct graf {
	int node, cost;
	graf *next;
} graf;

graf *a[MAXN];
int N, M;
int d[MAXN], pq[MAXN];

void inline add(int from, int to, int cost){
	graf *q = new graf;
	q -> node = to;
	q -> cost = cost;
	q -> next = a[from];
	a[from] = q;
}

void inline read(){
	freopen("dijkstra.in","r", stdin);
	freopen("dijkstra.out","w", stdout);
	scanf("%d %d", &N, &M);
	int to, from, cost;
	for(int i = 1; i <= M; i++){
		scanf("%d %d %d", &from, &to, &cost);
		add(from, to, cost);
	}
}

void inline swap(int a, int b) {
	int aux = pq[a];
	pq[a] = pq[b];
	pq[b] = aux;
}

void down_heapify(int index){
	int min = -1;
	while(true){
		min = index;
		if (2 * index <= pq[0] && d[pq[2 * index]] < d[pq[min]])
			min = 2 * index;
		if (2 * index + 1 <= pq[0] && d[pq[2 * index + 1]] < d[pq[min]])
			min = 2 * index + 1;
		if (index != min) {
			swap(index, min);
			index = min;
		} else
			break;
	}
}

void up_heapify(int index){
	int min = -1;
	while(true) {
		min = index;
		if (index > 1 && d[pq[index / 2]] > d[pq[index]])
			min = index / 2;
		if (index != min) {
			swap(index, min);
			index = min;
		} else
			break;
	}
}

int inline extract_min() {
	int result = pq[1];
	pq[1] = pq[pq[0]];
	pq[0]--;
	down_heapify(1);
	return result;
}

void decrease_priority(int node, int new_priority){
	int i = 1;
	while (i <= pq[0]){
		if(pq[i] == node){
			d[node] = new_priority;
			up_heapify(i);
			break;
		}
		i++;
	}
}

void dijkstra(){
	pq[0] = N;
	d[1] = 0;
	pq[1] = 1;
	for(int i = 2; i <= N; i++){
		d[i] = inf;
		pq[i] = i;
	}

	while(pq[0] > 0) {
		int min = extract_min();
		graf *g = a[min];
		while(g){
			int cost = g -> cost;
			int node = g -> node;
			if (cost + d[min] < d[node])
				decrease_priority(node, d[min] + cost);

			g = g -> next;
		}
	}
}

void inline print(){
	for(int i = 2; i <= N; i++)
		printf("%d ",d[i] == inf ? 0 : d[i]);
}

int main() {
	read();
	dijkstra();
	print();

	return 0;
}