#include<cstdio>
#include<vector>
#include<algorithm>
#define NMAX 50001
#define INF 0x3f3f3f3f
using namespace std;

int n, h[NMAX], x, nh, m, uz[NMAX], d[NMAX], poz[NMAX];
vector< pair<int, int> > A[NMAX];
int father(int x) {return x / 2;}
int left(int x) {return x * 2;}
int right(int x){return left(x) + 1;}
/*int get_min() {return h[1];}*/

void up_heap(int nod) {
	if(d[h[nod]] < d[h[father(nod)]] && nod > 1) {
		swap(poz[h[nod]], poz[h[father(nod)]]);
		swap(h[nod], h[father(nod)]);
		up_heap(father(nod));
	}
}

void down_heap(int nod) {
	int go = 0;
	if(left(nod) <= nh) 
		go = left(nod);
	if(d[h[left(nod)]] > d[h[right(nod)]] && right(nod) <= nh)
		go = right(nod);
	if(d[h[go]] >= d[h[nod]])
		go = 0;
	
	if(go) {
		swap(poz[h[nod]], poz[h[go]]);
		swap(h[nod], h[go]);
		down_heap(go);
	}
}

/*void make_heap() {
	for(int i = nh / 2; i >= 1; i--)
		down_heap(i);
}*/


void insert(int x, int nod) {
	h[++nh] = x; poz[x] = nh; up_heap(nh);
}

void dijkstra() {
	int nod;
	vector< pair<int, int> >::iterator it;
	for(nod = 1; nod <= n; nod++) {
		d[nod] = INF;
		poz[nod] = h[nod] = nod;
	}
	
	d[1] = 0;
	nh = n;
	while(nh) {
		nod = h[1];
		swap(h[1], h[nh]); swap(poz[h[1]], poz[h[nh]]);
		--nh;
		down_heap(poz[h[1]]);
		for( it = A[nod].begin(); it != A[nod].end(); ++it) 
			if(d[it->first] > d[nod] + it->second) {
				d[it->first] = d[nod] + it->second;
				up_heap(poz[it->first]);
			}
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d", &n, &m); 

	int x, y, z;
	for(int i = 1; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &z);
		A[x].push_back(make_pair(y, z));
	}
	
	dijkstra();
	for(int i = 2; i <= n; i++)	
		if(d[i] != INF)
			printf("%d ", d[i]);
		else printf("0 ");
	printf("\n");
	
	return 0;
}