# include <stdio.h>
const inf = 32000;
typedef struct nod {
			long key;
			nod *next;
		   };

long m, n, nh=0, cost[50010][50010], d[50010], viz[50010],heap[50010];
nod *a[50010];
void add ( int x,int y )
{
 nod * p;
	p = new nod;
	p->key = y;
	p->next = a[x];
	a[x] = p;
}

void cit ()
{
 int x,y,c;

	freopen ( "djikstra.in", "r", stdin );
	scanf ( "%d %d", &n, &m );
	for ( int i = 0; i < m; i++ )
		{
			scanf ( "%d %d %d", &x, &y, &c );
			add(x,y); cost[x][y] = c;d[y] = inf;d[x]=inf;
		}
	fclose ( stdin );
}

void minheap(int nod) //mentine proprietatea de min heap
{
	int st=2*nod, dr=2*nod+1, max = -1, aux;
	if (st<=nh && d[heap[st]] <= d[heap[nod]])
		max=st;
	if (dr<=nh && d[heap[dr]] < d[heap[max]])
		max=dr;
	if (max != -1 )
	{
		aux=heap[nod];
		heap[nod] = heap[max];
		heap[max] = aux;
		minheap(max);
	}
}

void push ( int v ) //insereaza elementul v in heap
{
	int aux;
	heap[++nh] = v;
	for (int i=nh; i>1; i= i>>1 )
		if (d[heap[i >> 1]] > d[heap[i]])
		{
		aux=heap[i >> 1];
		heap[i >> 1] = heap[i];
		heap[i] = aux;
		}
}

int pop () // scoate elementul minim din heap
{
	int rez = heap[1];
	heap[1] = heap[nh--];
	minheap(1);
	return rez;
}

void init ()
{
	int vertex = 1;
	viz[1] = 1;
	for ( nod *p = a[vertex]; p; p=p->next )
		 {
			d[p->key] = cost[vertex][p->key];
			push ( p->key );
		 }
}


void inbunatatire_drum ( int vf )
{
 for ( nod *p = a[vf]; p; p= p->next )
	if ( viz[p->key] == 0 )
		if ( d[p->key] > d[vf] + cost[vf][p->key] )
			d[p->key] = d[vf] + cost[vf][p->key];
	else
		p = p->next;
}

void djikstra ()
{
 int min;

	for ( int i = 0; i < n-1; i++ )
	 {
		min = pop ();
		viz[min] = 1;
		inbunatatire_drum(min);
	 }

}

void afish ()
{
	freopen ( "djikstra.out", "w", stdout );
	for ( int i = 1; i<= n; i++ )
		if ( d[i] != inf )
			printf ( "%d ", d[i] );
	fclose ( stdout );
}

int main ()
{
	cit ();
	init();
	djikstra();
	afish();
	return 0;
}