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

const long MAX = 50010;
vector< pair<long,long> > G[MAX];
long D[MAX], D_final[MAX], n,m;
bool U[MAX];

long *Arb;
long arb_st, arb_dr, arb_x;

void arb_set(long r, long st, long dr) { 
	Arb[r] = st;
	if ( st==dr ) return;
	long mij = (st+dr)/2;
	arb_set(2*r+1, st, mij);
    if ( mij<dr )
		arb_set(2*r+2, mij+1, dr);
}

void arb_init(long dim) {
	long k;
	for (k=1; k<=2*dim; k<<=1);
	Arb = new long[k];
	arb_set(0, 1, n);
}

void arb_update(long r, long st, long dr) {
	if ( st==dr ) return;
	long mij = (st+dr)/2;
	if ( arb_st<=mij ) arb_update(r*2+1, st, mij);
	if ( arb_dr>mij ) arb_update(r*2+2, mij+1, dr);
	if ( D[Arb[2*r+1]] <= D[Arb[2*r+2]] )
		Arb[r] = Arb[2*r+1];
	else
		Arb[r] = Arb[2*r+2];
}

void dijkstra() {
	memset(D, 0x3f, sizeof(D));

	D[1] = 0;
	arb_init(n);
	while ( 1 ) {
		long x = *Arb;
		if ( U[x] ) 
			break;

        U[x] = true;
		D_final[x] = D[x]; D[x] = 0x3f3f3f3f+1;
		arb_st = arb_dr = x;
		arb_update(0,1,n);
		for(vector< pair<long,long> >::iterator it=G[x].begin(); it!=G[x].end(); ++it)
			if ( D[it->first] > D_final[x] + it->second ) {
				D[it->first] = D_final[x] + it->second;
				arb_st = arb_dr = it->first;
				arb_update(0,1,n);
			}
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	scanf("%ld %ld", &n, &m);
	while ( m-- ) {
		long x,y,c;
		scanf("%ld %ld %ld", &x, &y, &c);
		G[x].push_back(make_pair(y,c));
	}

	dijkstra();

	freopen("dijkstra.out", "w", stdout);
	for (long i=2; i<=n; ++i)
		printf("%ld ", D_final[i]);
	return 0;
}