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

#define maxm 250002
#define maxn 66000
#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];
long poz2,val2;

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)>>1);
	fa_arbore( nod*2+1, ((st+dr)>>1)+1, dr);
}
void add_arbore( long nod, long st, long dr)
{
	if( poz2 > dr || poz2 < st ) return;
	
	if( st == dr) {arb[nod] = val2;return;}
	add_arbore( nod*2, st, ((st+dr)>>1));
	add_arbore( nod*2+1, ((st+dr)>>1)+1 , dr);
	
	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);
	poz2 = 1;
	val2 = 0;
	add_arbore(1,1,n);
	
	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;
		poz2 = nod;
		val2 = maxint;
		add_arbore( 1,1, n);
		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;
				poz2 = vec;
				val2 = min[vec];
				add_arbore( 1,1,n);
			}
			
		}
		
	}
}

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]]++;
		
	}
	return 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;
}