# 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[ dim ], 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;
}