# include <fstream>
# include <vector>
# include <queue>
# include <algorithm>

using namespace std;

const int maxn = 51000;
const int inf = 0x3f3f3f3f;
int n, m;
vector <int> G [ maxn ], C [ maxn ];
int gSize [ maxn ], dist [ maxn ];//, from [ maxn ];
bool viz [ maxn ];

priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > h;



void build_graph (){
	
	int i, x, y, c;
	ifstream f ( "dijkstra.in" );
	
	f >> n >> m;
	for ( i = 0; i < m; ++ i ){
		f >> x >> y >> c;
		G [ x ] . push_back ( y );
		C [ x ] . push_back ( c );
	}
	
	f . close ();
	
	for ( i = 1; i <= n; ++ i )
		gSize [ i ] = G [ i ] . size ();
	
}

void Dijkstra(){
	
	int i, minim;
	
	//init
	//for ( i = 2; i <= n; ++ i ){
		//dist [ i ] = inf;
		//from [ i ] = -1;
	//}
	memset(dist, 0x3f, 4*(n+2));
	dist [ 1 ] = 0;
	//from [ 1 ] = 0;
	h . push ( make_pair( 0 , 1 ) );
	
	//relax
	while ( ! h . empty() ){
		minim = h . top () . second;
		h . pop();
		if ( viz [ minim ] )	continue;
		viz [ minim ] = true;
		for ( i = 0; i < gSize [ minim ]; ++ i )
			if ( dist [ minim ] + C [ minim ] [ i ] < dist [ G [ minim ] [ i ] ] ){
				dist [ G [ minim ] [ i ] ] = dist [ minim ] + C [ minim ] [ i ];
				//from [ G [ minim ] [ i ] ] = minim;
				h . push ( make_pair( dist [ G [ minim ] [ i ] ], G [ minim ] [ i ] ) );
			}
	}
	
}

void afis (){
	
	ofstream g ( "dijkstra.out" );
	int i;
	
	for ( i = 2; i <= n; ++ i )
		if ( dist [ i ] != inf )
			g << dist [ i ] << ' ';
		else g << "0 ";
	g << '\n';
	
	g . close ();
	
}

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