# include <fstream>
 # include <algorithm>
 # include <vector>
 # include <queue>
 
 # define dim 50002
 # define dim2 250002
 # define inf 99999
 # define pb push_back
 
 using namespace std;
 
 ifstream f("dijkstra.in");
 ofstream g("dijkstra.out");
 
 vector <int> a[ dim2 ], c[ dim ];
 vector <int> drum( dim , inf );
 queue <int> q;
 
 int n, m;
 
 void completeaza();
 
 void citire()
 {
	 int i, x, y, cost;
	 f >> n >> m;
	 completeaza();
	 for ( i = 1 ; i <= m ; i++ )
	 {
		 f >> x >> y >> cost;
		 a[ x ].pb( y );
		 c[ x ][ y ] = cost;
	 }
 }
 
 void completeaza()
 {
	 int i, j;
	 for ( i = 1 ; i <= n ; i++ )
		 for ( j = 0 ; j <= n ; j++ )
			c[ i ].pb( inf ); 
 }
 
 void dijkstra()
 {
	 int i, x, xx;
	 x = 1;
	 drum[ x ] = 0;
	 q.push( x );
	 
	 while ( !q.empty() )
	 {
		 xx = q.front();
		 for ( i = 0 ; i < a[ xx ].size() ; i++ )
			 if ( drum[ xx ] + c[ xx ][ a[ xx ][ i ] ] < drum[ a[ xx ][ i ] ])
			 {
				 drum[ a[ xx ][ i ] ] = drum[ xx ] + c[ xx ][ a[ xx ][ i ] ];
				 q.push( a[ xx ][ i ] );
			 }
			 
			 q.pop();
	 }
	 
 }
 void afisare()
 {
	 int i, j;
	 /*for ( i = 1 ; i <= n ; i++ )
	 {
		 for ( j = 1 ; j <= n ; j++ )
			 g << c[ i ][ j ] << " ";
		 g << "\n";
	 }*/
	// g << "\n";
	 for ( i = 2 ; i <= n ; i++ )
		 if ( drum[ i ] == inf )
			 g << 0 << " ";
		 else
		 g << drum[ i ] << " ";
 }
 
 int main()
 {
	 citire();
	 dijkstra();
	 afisare();
	 return 0;
 }