#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define mp make_pair
#define pb push_back
#define N 50100
#define ls(st) st << 1
#define F first 
#define S second 
#define INF 0x3f3f3f3f


vector < pair <int, int> > a[N];
int n, m, k, poz[N], h[N], d[N];

void citire(), dijkstra();

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	citire();
	dijkstra();
int i;
	for (i = 2; i <= n; i++)
		printf("%d ", (d[i] != INF ? d[i] : 0));
	printf("\n");
	
	return 0;
}

void citire(){
int i, x, y, z;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++){
		scanf("%d %d %d", &x, &y, &z);
		a[x].pb(mp(y,z));
	}
}

void upheap(int w){
	while (w > 1 && (d[h[w]] > d[h[w>>1]])){
		swap(poz[h[w]], poz[h[w>>1]]);
		swap(h[w], h[w>>1]);
		w >>= 1;	
	}
}

void downheap(int w){
int son;
	while (ls(w) <= k){
		son = ls(w);
		if (son+1 <= k)
			if (d[h[son]] > d[h[son+1]])
				++son;
		if (d[h[w]] > d[h[son]]){
			swap(poz[h[w]], poz[h[son]]);
			swap(h[w], h[son]);
			w = son;
		}
		else
			return;
	} 
}

void dijkstra(){
int i, min, nod2, cost2;
	for (i = 2; i <= n; ++i) poz[i] = -1, d[i] = INF;
	poz[1] = 1; h[1] = 1; k = 1;

	while (k){
		min = h[1];
		swap(h[1], h[k]); poz[h[1]] = 1;
		--k;
		downheap(1);
		
		for (i = 0; i < a[min].size(); ++i){
			nod2 = a[min][i].F; cost2 = a[min][i].S;
			if (d[min] + cost2 < d[nod2]){
				d[nod2] = d[min] + cost2;
				if (poz[nod2] == -1){
					poz[nod2] = ++k;
					h[k] = nod2;
					upheap(k);
				}
				else
					upheap(poz[nod2]);
			}
		}
	}
}