#include <cstdio>

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

int n;
long 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 aux= h[k];
	while (k>1 && d[aux]< d[ h[k/2] ])
	{	h[k]= h[k/2];
		k=k/2;
	}
	h[k]=aux;
}

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); 
	}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);
		--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%ld", &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;
	/*
		q=new nod;
		q->v=x;			q->c=c;
		q->next=G[y];	G[y]=q;
	*/
	}
	
	Dijkstra();
	
	for ( int i = 2; i <= n; ++i )  
         printf("%d ", d[i] == inf ? 0 : d[i]);  
     //printf("\n"); 
	
	fclose(stdout);
	return 0;
}