#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define maxm 500002
#define maxn 33000
#define maxint 2000000000

long v[maxm][3];
long s[maxn],nr[maxn];
long min[maxn];
long arb[maxn*2];
long cine[maxn*2];
long sel[maxn];

int cmpvec(const void *a, const void *b)
{
	int *c = (int *)a;
	int *d = (int *)b;
	return c[0] - d[0];
	
}
void fa_arbore(long nod, long st, long dr)
{
	arb[nod] = maxint;
	cine[nod] = st;
	if( st == dr) return;
	fa_arbore( nod*2, st, (st+dr)/2);
	fa_arbore( nod*2+1, (st+dr)/2+1, dr);
}
void add_arbore( long nod, long st, long dr, long poz, long val)
{
	if( poz > dr || poz < st ) return;
	
	if( st == dr) {arb[nod] = val;return;}
	add_arbore( nod*2, st, (st+dr)/2, poz, val);
	add_arbore( nod*2+1, (st+dr)/2+1, dr, poz, val);
	
	arb[nod] = arb[nod*2];
	cine[nod] = cine[nod*2];
	if( arb[nod] > arb[nod*2+1])
	{
		arb[nod] = arb[nod*2+1];
		cine[nod] = cine[nod*2+1];
	}
	
	
}
void dijkstra(long n)
{
	for( long i = 2; i <= n; ++i)
		min[i] = maxint;
	fa_arbore(1,1,n);
	add_arbore(1,1,n,1,0);
	
	for( long ii = 1; ii <= n; ++ii)
	{
		long nod = cine[1];
		long val = arb[1];
		sel[nod] = 1;
		if( val == maxint)
			break;
		min[nod] = val;
		add_arbore( 1,1, n, nod, maxint);
		for( long i = s[nod]; i < s[nod+1]; ++i)
		{
			long vec = v[i][1];
			if( sel[ vec ] == 1) continue;
			if( min[vec] > v[i][2] + val)
			{
				min[vec] = v[i][2] + val;
				add_arbore( 1,1,n, vec, min[vec]);
			}
			
		}
		
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	long n,m;
	
	scanf("%ld %ld",&n,&m);
	
	for( long i = 1; i <= m; ++i)
	{
		scanf("%ld %ld %ld",&v[i][0],&v[i][1],&v[i][2]);
		nr[v[i][0]]++;
		
		
	}
	
	qsort( v+1,m,sizeof(v[0]), cmpvec);
	s[0] = 1;
	for( long i = 1; i<= n+1; ++i)
		s[i] = s[i-1] + nr[i-1];
	
	dijkstra(n);
	for( long i = 2; i <= n; ++i)
	{
		if( min[i] == maxint)
			printf("0 ");
		else printf("%ld ",min[i]);
	}
	
	return 0;
}