#include<cstdio>
#include<queue>
#include<vector>
#include<ctime>
#include<cstdlib>
#define INfile "dijkstra.in"
#define OUTfile "dijkstra.out"
#define NMAX 50002

using namespace std ;

int N , M ;

vector < int > d ( NMAX , 999999 ) ;

struct Compare 
{
	bool operator () ( int i , int j ) 
	{
	return d [ i ] < d [ j ] ;
	}
} ;

vector < pair < int , int > > Nod [ NMAX ] ; 
char FR [ NMAX ] ;

void read () ;
void write () ;
void solve () ;

int main () 
{
	freopen ( INfile , "r" , stdin ) ;
	freopen ( OUTfile , "w" , stdout ) ;
	
	//double cc = clock(); 
	read () ;
	
	solve () ;

	write () ;
	//double tt = clock() ;
	//printf("\n%lf" , (tt-cc)/CLK_TCK ) ;
	return 0 ;
}


void read () 
{
	int i , x , y , c ;
	scanf ( "%d%d" , & N , & M ) ;
	for ( i = 1 ; i <= M ; ++ i ) 
	{
		scanf ( "%d%d%d" , & x , & y , & c ) ;
		pair < int , int > NOD ;
		NOD.first = y;
		NOD.second = c;
		Nod [ x ].push_back ( NOD ) ;
	}
}


void solve() 
{
	priority_queue < int > Q ;
	pair < int , int > P ;
	int k , lg , i ;
	d [ 1 ] = 0 ;
	FR [ 1 ] = 1 ;
	Q.push ( 1 ) ;
	while ( ! Q.empty() ) 
	{
		k = Q.top () ;
		Q.pop () ;
		FR [ k ] = 0 ;
		lg = Nod [ k ].size () ;
		for ( i = 0 ; i < lg ; ++ i)
		{
			P = Nod [ k ][ i ] ;
			if ( d [ k ] + P.second < d [ P.first ] ) 
			{
				d [ P.first ] = d [ k ] + P.second ;
				if ( FR [ P.first ] == 0 )
				{
					Q.push ( P.first ) ;
					FR [ P.first ] = 1 ;
				}
			}
		}
	}
}

void write () 
{
	int i ;
	for ( i = 2 ; i <= N ; ++ i ) 
		printf ( "%d " , d [ i ] ) ;
	printf ( "\n" ) ;
}