#include<stdio.h>
#include<vector>
using namespace std;

#define NMAX 50000
#define inf 1<<30

typedef struct{
	int nod,dist;
}q;

vector< q > G[NMAX];

int N,M;
int sf=0;

int D[NMAX];
int H[NMAX],P[NMAX];

void swap( int p1,int p2 )
{
	H[p1]^=H[p2]; H[p2]^=H[p1]; H[p1]^=H[p2];
}

void upp( int poz )
{
	int father=poz>>1;
	int d1=D[poz];
	int d2=D[father];
	
	if( father>=1 )
	{
		if( d1<d2 )
		{
			P[ H[poz] ]=father;
			P[ H[father] ]=poz;
			swap( poz,father );
			if( father!=1 )
			upp( father );
		}
	}
}
	
void down( int poz )
{
	int lson=poz<<1;
	int rson=lson+1;
	int ctrl=poz;
	
	if( lson<=sf )
	{
		if( D[lson]<D[ctrl] )
			ctrl=lson;
	}
	if( rson<=sf )
	{
		if( D[rson]<D[ctrl] )
			ctrl=rson;
	}
	
	if( ctrl!=poz )
	{
		P[ H[poz] ]=ctrl;
		P[ H[ctrl] ]=poz;
		swap( ctrl,poz );
		
		if( ctrl!=sf )
		down( ctrl );
	}
}
	
void djikstra()
{
	int i,nod;
	for( i=2; i<=N; ++i )
		D[i]=inf,P[i]=-1;
	D[1]=0;
	
	int D1,D2,D3;
	
	sf=1;
	H[sf]=P[sf]=1;
	
	vector< q >::iterator it;
	
	while( sf )
	{
		nod=H[1];
		D1=D[nod];
		
		P[ H[sf] ]=1;
		swap( 1, sf );
		--sf;
		down(1);
		
		for( it=G[nod].begin(); it!=G[nod].end(); ++it )
		{
			D2=it->dist;
			D3=D[ it->nod ];
			
			if( D1+D2 <= D3 )
			{
				D[ it->nod ]=D1+D2;
				
				if( P[ it->nod ]==-1 )
				{
					H[++sf]=it->nod;
					P[it->nod]=sf;
					upp(sf);
				}
				else
				{
					upp( P[it->nod] );
				}
			}
		}
	
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	
	int i;
	int a1,a2,a3;
	for(i=1; i<=M; ++i)
	{
		scanf("%d%d%d",&a1,&a2,&a3);
		
		q X;
		X.nod=a2;
		X.dist=a3;
		
		G[a1].push_back(X);
	}
	
	djikstra();
	
	for( i=2; i<=N; ++i )
		printf("%d ",D[i]!=inf?D[i]:0);
	printf("\n");
	
	return 0;
}