# include <cstdio>
# include <vector>

using namespace std;

const int maxn = 51000, inf = 2000000003;
int n, m;
vector <int> G [ maxn ], C [ maxn ];
int gSize [ maxn ], dist [ maxn ], from [ maxn ];
int heap [ maxn ], hSize, pos [ maxn ];
int viz [ maxn ];

void build_graph (){
	
	int i, x, y, c;
	FILE *f = fopen ( "dijkstra.in", "rt" );
	
	fscanf ( f, "%d%d", &n , &m);
	for ( i = 0; i < m; ++ i ){
		fscanf ( f, "%d%d%d",  &x , &y, &c );
		G [ x ] . push_back ( y );
		C [ x ] . push_back ( c );
	}
	
	fclose ( f );
	
	for ( i = 1; i <= n; ++ i )
		gSize [ i ] = G [ i ] . size ();
	
}

void heapify ( int ps ){
	
	int md, mn, en, ips = ps;
	en = heap [ ps ];
	bool ok = true;
	while ( ok ){
		ok = false;
		md = dist [ heap [ ps ] ];
		mn = heap [ ps ];
		if ( ( ps <<= 1 ) <= hSize )
			if ( dist [ heap [ ps ] ] < md ){
				md = dist [ heap [ ps ] ];
				mn = heap [ ps ];
			}
		if ( ( ps |= 1 ) <= hSize )
			if ( dist [ heap [ ps ] ] < md ){
				md = dist [ heap [ ps ] ];
				mn = heap [ ps ];
			}
		if ( pos [ mn ] != ips ){
			swap ( heap [ pos [ mn ] ], heap [ ips ] );
			ips = ps = pos [ mn ];
			swap ( pos [ en ], pos [ mn ] );
			ok = true;
		}
	}
	
}

int extract_min(){
	
	int nd;
	nd = heap [ 1 ];
	heap [ 1 ] = heap [ hSize ];
	pos [ heap [ hSize ] ] = 1;
	-- hSize;
	viz [ nd ] = 2;
	
	heapify ( 1 );
	
	return nd;
}

void upHeap ( int ps ){
	
	int en, mn;
	en = heap [ ps ];
	while ( ps && dist [ heap [ ps / 2 ] ] > dist [ heap [ ps ] ] ){
		mn = heap [ ps / 2 ];
		swap ( heap [ ps ], heap [ ps / 2 ] );
		swap ( pos [ mn ], pos [ en ] );
		ps /= 2;
	}
	
}

void update_heap ( int nd ){
	
	upHeap ( pos [ nd ] );
	
}

void insert_heap ( int nd ){
	
	++ hSize;
	heap [ hSize ] = nd;
	pos [ nd ] = hSize;
	upHeap ( hSize );
	
}

void Dijkstra(){
	
	int i, minim;
	
	//init
	for ( i = 2; i <= n; ++ i ){
		dist [ i ] = inf;
		from [ i ] = -1;
	}
	dist [ 1 ] = 0;
	from [ 1 ] = 0;
	heap [ 1 ] = 1;
	hSize = 1;
	pos [ 1 ] =  1;
	
	//relax
	while ( hSize > 0 ){
		minim = extract_min ();  // removes the minimum dist node nd and returns nd; also decreases hSize and makes viz [ nd ] == 2
		for ( i = 0; i < gSize [ minim ]; ++ i )
			if ( viz [ G [ minim ] [ i ] ] < 2 && dist [ minim ] + C [ minim ] [ i ] < dist [ G [ minim ] [ i ] ] ){
				dist [ G [ minim ] [ i ] ] = dist [ minim ] + C [ minim ] [ i ];
				from [ G [ minim ] [ i ] ] = minim;
				if ( ! viz [ G [ minim ] [ i ] ] ){
					insert_heap ( G [ minim ] [ i ] );
					viz [ G [ minim ] [ i ] ] = 1;
				}
				else update_heap ( G [ minim ] [ i ] );
			}
	}
	
}

void afis (){
	
	FILE *g = fopen ( "dijkstra.out", "wt" );
	int i;
	
	for ( i = 2; i <= n; ++ i )
		if ( dist [ i ] != inf )
			fprintf ( g, "%d ", dist [ i ] );
		else fprintf ( g, "0 " );
	fprintf ( g, "\n" );
	
	fclose ( g );
	
}

int main (){
	
	build_graph ();
	Dijkstra ();
	afis ();
	
	return 0;
	
}