#include<cstdio>
#include<algorithm>
#include<vector>
#include<list>
#define T ((i) / 2)
#define R ((i) * 2)
#define L ((i) * 2 + 1)
#define NMAX 50001
using namespace std;

vector< pair<int, int> > A[NMAX];
int h[NMAX], d[NMAX], poz[NMAX], n, m, nh;
const int INF = 0x3f3f3f3f;

void up_heap(int i) {
	if(i > 1) {
		if(d[h[i]] < d[h[T]]) {
			swap( h[i], h[T] );
			swap( poz[h[i]], poz[h[T]] );
			up_heap(T);
		}
	}
}

void down_heap(int i) {
	int m = i; 
	if(L <= nh && d[h[L]] > d[h[m]])
		m = L;
	if(R <= nh && d[h[R]] > d[h[m]])
		m = R;
	if( m != i ) {
		swap(h[i], h[m]);
		swap(poz[h[i]], poz[h[m]]);
		down_heap(m);
	}

}

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", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);
	
	scanf("%d %d", &n, &m);
	
	int x, y, z;
	for(int i = 0; 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;
}