#include <fstream>
#include <vector>
using namespace std;
ifstream cin( "dijkstra.in" ); ofstream cout( "dijkstra.out" );
int d[ 50001 ], s[ 50001 ], p[ 50001 ];
int x, y, cost, n, m, t, dMin, k, teste; 
vector<int> v[ 50001 ], c[ 50001 ];
int main()
{	int i, j;
	cin >> n >> m;
	for ( i = 1; i <= n; i++ ) d[ i ] = 9999999;
	for ( i = 1; i <= m; i++ )
	{	cin >> x >> y >> cost;
		if ( x == 1 ) d[ y ] = cost;
		v[ x ].push_back( y );
		c[ x ].push_back( cost );
	}
	s[ 1 ] = 1; d[ 1 ] = 0;
	for ( j = 1; j < n; j++ )
	{	dMin = 9999999;
		for ( i = 1; i <= n; i++ )
			if ( dMin > d[ i ] && s[ i ] < 1 ) {dMin = d[ i ]; k = i;}
            s[ k ] = 1;
			p[ i ] = k;
		for ( i = 0; i < v[ k ].size(); i++ )
			if ( s[ v[ k ][ i ] ] < 1 && d[ v[ k ][ i ] ] > d[ k ] + c[ k ][ i ] )
				d[ v[ k ][ i ] ] = d[ k ] + c[ k ][ i ];
	}
	for ( i = 2; i <= n; i++ )
		if ( d[ i ] == 9999999 ) cout << "0 "; else cout << d[ i ] << " ";
}