#include <cstdio>

const int maxn = 50001;
const int inf = 1 << 30;

int n, m;

struct nod { int v,c;
			nod *next; } *G[maxn];

int d[maxn],h[maxn],poz[maxn];
int lh=0;

inline void swap( int x, int y)
{
	int aux= h[x];
	h[x] = h[y];
	h[y] = aux;
	poz[ h[x] ] = x;
	poz[ h[y] ] = y;
}

void urca( int k)
{
	int t;
	while (k>1) 
	{	t= k/2;
		if(d[h[k]]< d[ h[t] ])
		{	swap(k,t);
			k=t;
		}	
		else
		 	k=1;
	}
}

void coboara( int k)
{
	int son;
	do{
		son=0;
		if (2*k< lh)
		{	son=2*k;
		 	if (son+1<= lh && d[ h[son+1] ]< d[ h[son]])
		 		son++;
		 	if( !(d[h[son]] < d[h[k]]) )
		 		son=0;
		}
		if(son)
			swap(son,k); 
		k=son;
	}while (son);
}

void Dijkstra()
{
	for( int i=2; i<=n; ++i)
		d[i]= inf, poz[i]= -1;
	poz[1] =1;
	h[++lh] =1;
	
	while(lh)
	{
		int min= h[1];
		swap(1,lh);
		poz[h[1]]=1;
		--lh;
		coboara(1);
		
		nod *q= G[min];
		
		while( q)
		{	if (d[q->v] > d[min] + q->c )
			{	d[q->v] = d[min] + q->c;
				if ( poz[q->v] != -1)  //daca se gaseste in heap
					urca( poz[q->v] ) ; 
				else
				{	h[++lh] = q->v;
					poz[ h[lh] ] = lh;
					urca (lh);
				}
			}
			q = q->next;
		}
	}
}


int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d", &n,&m);
	nod *q;
	int i,x,y,c;
	for(i=1; i<=m; ++i)
	{	scanf("%d%d%d", &x,&y,&c);
	
		q=new nod;
		q->v=y;			q->c=c;
		q->next=G[x];	G[x]=q;
	}
	fclose(stdin);
	
	Dijkstra();
	
	for ( int i = 2; i <= n; ++i )  
         if( d[i] == inf) 
         	printf("0 ");
         else
         	printf("%d ", d[i]);  
    printf("\n"); 
	
	fclose(stdout);
	return 0;
}