#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<iostream>

#include<vector>
#include<set>
#include<string.h>

#define maxint 2000000000
#define maxn 1024



using namespace std;



/*typedef struct edge{
	int node, price;
	edge ( int a, int b)
	{
		node = a;
		price = b;
	}
};*/

long m[ maxn][ maxn];
long sel[50001];

class graph{
	
public :
	vector< vector < int > > list;
	vector< vector < int > > cost;
	vector< vector <int> > mat;
	int size; // number of nodes (usually n)
	char type; // what kind of storage are we using 0 for list of neighbours 1 for li
	
private:
	
	int add_edge_matrix( const int &a, const int &b, const int& cost)
	{
		//this ads an edge to the matrix
		// if the values are greater than the size of the matrix then it returns 1
		/// if edge allready exists in matrix -> it returns 0 
		int ret = 0;
		if( a > size || b > size)
			return 1;
		if( mat[a][b] != -1)
			ret = 2;
		mat[ a][b] = cost;
		
		return ret;
		
	}
public:
	
	int add_edge_list( const int &a, const int &b, const int& cost2)
	{
		//this ads an edge to the matrix
		// if the values are greater than the size of the matrix then it returns 1
		// else returns 0
		
		if( a > size || b > size)
			return 1;
		
		/*edge *temp = new edge();
		(*temp).node = b;
		(*temp).price = cost2;*/
		
		list[a].push_back( b );
		cost[a].push_back( cost2 );
		//list[a].insert( list[a].end(), *( new edge(b,cost2)) );
		
		
		return 0;
		
	}
	
	
	public:
	
	graph(const int& get_size,int way  = 0)	{
		type = way;
		size = get_size;
		
		vector<int> a;
		//a.reserve();
		
		if( way == 0) 		{
			
			//we are creating the list of neighbours O(m)
			
			
			list.assign( size + 1, a);
			cost.assign( size + 1, a);
			
		}
		if( way == 1)	{
			// we create the matrix of neighbours O(n^2)
			
			vector<int> *a = new vector<int>(-1,size + 1);
			mat.assign( size+1, *a);
			delete a;
			
			
		}
			
	}
	void add_all_edges( const int& m, int *ed)
	{
		
		int curent = 1, a = 0, last = 0;
		
		solutie oki
		int *first = new int[m];
		int *second = new int[m];
		//int *cos = new int[m];
		
		for( long i = 0; i < m; ++i)
			first[i] = ed[ i * 3 ] , second[i] = ed[i * 3 + 1], cos[i] = ed[i * 3 + 2];
		
			
		while( a < m )
		{
			while( first[ a ] != curent)
			{
				list[ curent ].assign( second + last , second + a );
				cost[ curent ].assign( cos + last , cos + a );
				last = a;
				curent++;
			}
			++a;
			
		}
		list[ curent ].assign( second + last , second + a );
		cost[ curent ].assign( cos + last , cos + a );
		
		delete [] first;
		delete [] second;
		//delete [] cos;
		
		
	}

	int add_edge( const int &a, const int &b, const int &c)
	{
		int rez;
		
		if( type %2 == 0) // if type == 2 we add to both matrix and list if 0 only to list if 1 only to matrix
		{
			rez = add_edge_list( a, b, c);
			if( type == 0)
				return rez;
		}
		
		return add_edge_matrix( a, b, c);
		
	}
	
	void print_list()
	{
		printf("%d\n", size);
		for( long i = 1; i <= size; ++i)
		{
			printf("%ld : ", i );
			long temp_n = list[i].size();
			for( long j = 0; j < temp_n; ++j)
			{
				printf(" ( %d, %d )" , list[i][j] , cost[i][j]);
			}
			printf("\n");
		}
	}
};

class arb_int{
	
private:
	int size;
	int *vec;
	int *index;
	int *who;
	short int type;
	/* type = 0 -> min_tree
	   type = 1 -> sum_tree
	
	*/
	
	int real_size( const int& n){
		// determines the size of the tree it has to be around twice as big as the information used
		int w = 1;
		while( w < n)
			w <<= 1;
		w <<= 1;
		return w;
		
		
	}
public:
	
	arb_int ( const int& a, int typ = 0)	{
		
		size = real_size(a);
		vec = new int[ size ];
		int *info = new int[ a + 1];
		index = new int[ a + 1 ];
		type = typ;
		
		for( int i = 0; i <= a; ++i)
			info[i] = maxint;
			
		

		if( type == 0)
		{
			who = new int[ size ];
		}
		create( 1, 1, a, info);
	}
	
	arb_int ( const int& a, int* info , int typ = 0)	{
		size = real_size(a);
		type = typ;
		vec = new int[ size ];
		index = new int[ a + 1 ];
		if( type == 0)
		{
			who = new int[ size ];
		}
		
		create( 1, 1, a, info);
		
	}
	
	
	inline void update_info( const int& nod)
	{
		if( type == 1){
			vec[ nod ] = vec[ nod << 1] + vec[ (nod << 1) + 1];
			return ;
		}
		if( type == 0){
			vec[ nod ] = vec[ nod << 1];
			who[ nod ] = who[ nod << 1];
			if( vec[ (nod << 1) + 1] < vec[ nod] )
				vec[ nod] = vec[ (nod << 1) + 1], who[ nod ] = who [ (nod << 1) + 1];
			return;
		}
			
	}
	
	void create( const int& nod, const int &left, const int &right, int* info)
	{
		if( left == right)
		{
			index[ left ] = nod;
			vec[ nod ] = info[ left ];
			if( type == 0)
				who[ nod ] = left;
			return;
		}
		
		create( (nod << 1), left, ( left + right) >> 1, info);
		create( (nod << 1) + 1, (( left + right) >> 1) + 1, right, info);
		
		update_info( nod );
		
	}
	
	void modify( const int& nod, const int& new_info )
	{
		int temp_nod = index[ nod ];
		vec[ temp_nod ] = new_info;
		temp_nod >>= 1;
		while( temp_nod )
		{
			update_info( temp_nod);
			temp_nod >>= 1;
		}
		
	}
	
	int get_top()
	{
		return vec[ 1 ];
	}
	int who_top()
	{
		return who[ 1 ];
	}
	void eliminate_top()
	{
		modify( who[ 1 ], maxint );
	}
	int get_element( const int &nod)
	{
		return vec[ index[ nod] ];
	}
	
	
	
};






int cmp_int( const void *a, const void *b)
{
	int *c = (int *)a;
	int	*d = (int *)b;
	if( c[0] < d[0])
		return false;
	if( c[0] > d[0])
		return true;
	if( c[1] < d[1])
		return false;
	return true;
}
int main()
{
	int bla = 0;
	if ( bla == 1)
	{
		long test[3][3];
		test[0][0] = 1, test[0][1] = 3, test[0][2] = 4;
		test[1][0] = 3, test[1][1] = 2, test[1][2] = 2;
		test[2][0] = 2, test[2][1] = 5, test[2][2] = 6;
		qsort( test,3, sizeof(test[0] ) , cmp_int);
		return 0;
	}
	if( bla == 0){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	long n,m;
	
	scanf("%ld %ld",&n,&m);
	graph g(n,0);
	arb_int arb( n ); 
	int rez[64 * 1024];
	memset( rez, 0, sizeof(rez));
	int *edge1;
	edge1 = new int[m * 3];
	for( long i = 0; i < m; ++i)
	{
		
		scanf("%d %d %d",&edge1[i * 3 ], &edge1[i * 3 + 1], &edge1[ i * 3 + 2]);
		
		if( edge1[i * 3 ] == 1)
			arb.modify( edge1[i * 3 + 1], edge1[i * 3 + 2]);
				
	}
	qsort( edge1,m, sizeof(int[3] ) , cmp_int);
	g.add_all_edges( m , edge1);
	delete [] edge1 ;
	arb.modify( 1, maxint + 1);
	
	//g.print_list();
	
	sel[1] = 1;
	
	for( long i = 1; i < n; ++i)
	{
		long curent = arb.who_top();
		long value = arb.get_top();
		if( value >= maxint)
			break;
		rez[ curent ] = value;
		sel[ curent ] = 1;
		//g.print_list();
		arb.eliminate_top();
		for( unsigned int i = 0; i < g.list[ curent ].size(); ++i)
		{
			int neib = g.list[ curent ][i] ;
			if( sel[ neib ] != 0) continue;
			if( arb.get_element( neib) > value + g.cost[ curent][i] )
				arb.modify( neib, value + g.cost[ curent][i]);
		}
		
		
	}
	
	for( long i = 2; i <= n; ++i)
	{
		printf("%d ",rez[i]);
	}
	printf("\n");
	
	
	
	
	}
	
	return 0;
}