# 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;
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 ();
	
}

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

void downHeap ( int pos ){
	int mn, md;
	bool ok = true;
	mn = pos;
	md = dist [ heap [ mn ] ];
	while ( ok ){
		ok = false;
		if ( pos * 2 <= hSize && dist [ heap [ pos * 2 ] ] < md ){
			md = dist [ heap [ pos * 2 ] ];
			mn = pos * 2;
		}
		if ( 1 + pos * 2 <= hSize && dist [ heap [ 1 + pos * 2 ] ] < md ){
			md = dist [ heap [ 1 + pos * 2 ] ];
			mn = 1 + pos * 2;
		}
		if ( mn != pos ){
			swap ( heap [ pos ], heap [ mn ] );
			ok = 1;
			pos = mn;
		}
	}
}

void make_heap (){
	int i;
	for ( i = hSize/2; i > 0; -- i )
		downHeap ( i );
}

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;
		
	//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 ] ] ){
					heap [ ++ hSize ] = G [ minim ] [ i ];
					viz [ G [ minim ] [ i ] ] = 1;
				}
			}
		make_heap ();
	}
	
}

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;
	
}